1// Copyright 2009 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28import { CodeMap, CodeEntry } from "./codemap.mjs";
29import { ConsArray } from "./consarray.mjs";
30import { WebInspector } from "./sourcemap.mjs";
31
32// Used to associate log entries with source positions in scripts.
33// TODO: move to separate modules
34export class SourcePosition {
35  script = null;
36  line = -1;
37  column = -1;
38  entries = [];
39  isFunction = false;
40  originalPosition = undefined;
41
42  constructor(script, line, column) {
43    this.script = script;
44    this.line = line;
45    this.column = column;
46  }
47
48  addEntry(entry) {
49    this.entries.push(entry);
50  }
51
52  toString() {
53    return `${this.script.name}:${this.line}:${this.column}`;
54  }
55
56  get functionPosition() {
57    // TODO(cbruni)
58    return undefined;
59  }
60
61  get toolTipDict() {
62    return {
63      title: this.toString(),
64      __this__: this,
65      script: this.script,
66      entries: this.entries,
67    }
68  }
69}
70
71export class Script {
72  url;
73  source;
74  name;
75  sourcePosition = undefined;
76  // Map<line, Map<column, SourcePosition>>
77  lineToColumn = new Map();
78  _entries = [];
79  _sourceMapState = "unknown";
80
81  constructor(id) {
82    this.id = id;
83    this.sourcePositions = [];
84  }
85
86  update(url, source) {
87    this.url = url;
88    this.name = Script.getShortestUniqueName(url, this);
89    this.source = source;
90  }
91
92  get length() {
93    return this.source.length;
94  }
95
96  get entries() {
97    return this._entries;
98  }
99
100  get startLine() {
101    return this.sourcePosition?.line ?? 1;
102  }
103
104  get sourceMapState() {
105    return this._sourceMapState;
106  }
107
108  findFunctionSourcePosition(sourcePosition) {
109    // TODO(cbruni) implmenent
110    return undefined;
111  }
112
113  addSourcePosition(line, column, entry) {
114    let sourcePosition = this.lineToColumn.get(line)?.get(column);
115    if (sourcePosition === undefined) {
116      sourcePosition = new SourcePosition(this, line, column,)
117      this._addSourcePosition(line, column, sourcePosition);
118    }
119    if (this.sourcePosition === undefined && entry.entry?.type === "Script") {
120      // Mark the source position of scripts, for inline scripts which don't
121      // start at line 1.
122      this.sourcePosition = sourcePosition;
123    }
124    sourcePosition.addEntry(entry);
125    this._entries.push(entry);
126    return sourcePosition;
127  }
128
129  _addSourcePosition(line, column, sourcePosition) {
130    let columnToSourcePosition;
131    if (this.lineToColumn.has(line)) {
132      columnToSourcePosition = this.lineToColumn.get(line);
133    } else {
134      columnToSourcePosition = new Map();
135      this.lineToColumn.set(line, columnToSourcePosition);
136    }
137    this.sourcePositions.push(sourcePosition);
138    columnToSourcePosition.set(column, sourcePosition);
139  }
140
141  toString() {
142    return `Script(${this.id}): ${this.name}`;
143  }
144
145  get toolTipDict() {
146    return {
147      title: this.toString(),
148      __this__: this,
149      id: this.id,
150      url: this.url,
151      source: this.source,
152      sourcePositions: this.sourcePositions
153    }
154  }
155
156  static getShortestUniqueName(url, script) {
157    const parts = url.split('/');
158    const filename = parts[parts.length -1];
159    const dict = this._dict ?? (this._dict = new Map());
160    const matchingScripts = dict.get(filename);
161    if (matchingScripts == undefined) {
162      dict.set(filename, [script]);
163      return filename;
164    }
165    // TODO: find shortest unique substring
166    // Update all matching scripts to have a unique filename again.
167    for (let matchingScript of matchingScripts) {
168      matchingScript.name = script.url
169    }
170    matchingScripts.push(script);
171    return url;
172  }
173
174  ensureSourceMapCalculated(sourceMapFetchPrefix=undefined) {
175    if (this._sourceMapState !== "unknown") return;
176
177    const sourceMapURLMatch =
178        this.source.match(/\/\/# sourceMappingURL=(.*)\n/);
179    if (!sourceMapURLMatch) {
180      this._sourceMapState = "none";
181      return;
182    }
183
184    this._sourceMapState = "loading";
185    let sourceMapURL = sourceMapURLMatch[1];
186    (async () => {
187      try {
188        let sourceMapPayload;
189        try {
190          sourceMapPayload = await fetch(sourceMapURL);
191        } catch (e) {
192          if (e instanceof TypeError && sourceMapFetchPrefix) {
193            // Try again with fetch prefix.
194            // TODO(leszeks): Remove the retry once the prefix is
195            // configurable.
196            sourceMapPayload =
197                await fetch(sourceMapFetchPrefix + sourceMapURL);
198          } else {
199            throw e;
200          }
201        }
202        sourceMapPayload = await sourceMapPayload.text();
203
204        if (sourceMapPayload.startsWith(')]}')) {
205          sourceMapPayload =
206              sourceMapPayload.substring(sourceMapPayload.indexOf('\n'));
207        }
208        sourceMapPayload = JSON.parse(sourceMapPayload);
209        const sourceMap =
210            new WebInspector.SourceMap(sourceMapURL, sourceMapPayload);
211
212        const startLine = this.startLine;
213        for (const sourcePosition of this.sourcePositions) {
214          const line = sourcePosition.line - startLine;
215          const column = sourcePosition.column - 1;
216          const mapping = sourceMap.findEntry(line, column);
217          if (mapping) {
218            sourcePosition.originalPosition = {
219              source: new URL(mapping[2], sourceMapURL).href,
220              line: mapping[3] + 1,
221              column: mapping[4] + 1
222            };
223          } else {
224            sourcePosition.originalPosition = {source: null, line:0, column:0};
225          }
226        }
227        this._sourceMapState = "loaded";
228      } catch (e) {
229        console.error(e);
230        this._sourceMapState = "failed";
231      }
232    })();
233  }
234}
235
236
237class SourceInfo {
238  script;
239  start;
240  end;
241  positions;
242  inlined;
243  fns;
244  disassemble;
245
246  setSourcePositionInfo(script, startPos, endPos, sourcePositionTable, inliningPositions, inlinedFunctions) {
247    this.script = script;
248    this.start = startPos;
249    this.end = endPos;
250    this.positions = sourcePositionTable;
251    this.inlined = inliningPositions;
252    this.fns = inlinedFunctions;
253  }
254
255  setDisassemble(code) {
256    this.disassemble = code;
257  }
258
259  getSourceCode() {
260    return this.script.source?.substring(this.start, this.end);
261  }
262}
263
264/**
265 * Creates a profile object for processing profiling-related events
266 * and calculating function execution times.
267 *
268 * @constructor
269 */
270export class Profile {
271  codeMap_ = new CodeMap();
272  topDownTree_ = new CallTree();
273  bottomUpTree_ = new CallTree();
274  c_entries_ = {};
275  scripts_ = [];
276  urlToScript_ = new Map();
277
278  serializeVMSymbols() {
279    let result = this.codeMap_.getAllStaticEntriesWithAddresses();
280    result.concat(this.codeMap_.getAllLibraryEntriesWithAddresses())
281    return result.map(([startAddress, codeEntry]) => {
282      return [codeEntry.getName(), startAddress, startAddress + codeEntry.size]
283    });
284  }
285
286  /**
287   * Returns whether a function with the specified name must be skipped.
288   * Should be overridden by subclasses.
289   *
290   * @param {string} name Function name.
291   */
292  skipThisFunction(name) {
293    return false;
294  }
295
296  /**
297   * Enum for profiler operations that involve looking up existing
298   * code entries.
299   *
300   * @enum {number}
301   */
302  static Operation = {
303    MOVE: 0,
304    DELETE: 1,
305    TICK: 2
306  }
307
308  /**
309   * Enum for code state regarding its dynamic optimization.
310   *
311   * @enum {number}
312   */
313  static CodeState = {
314    COMPILED: 0,
315    IGNITION: 1,
316    BASELINE: 2,
317    TURBOPROP: 4,
318    TURBOFAN: 5,
319  }
320
321  static VMState = {
322    JS: 0,
323    GC: 1,
324    PARSER: 2,
325    BYTECODE_COMPILER: 3,
326    // TODO(cbruni): add BASELINE_COMPILER
327    COMPILER: 4,
328    OTHER: 5,
329    EXTERNAL: 6,
330    IDLE: 7,
331  }
332
333  static CodeType = {
334    CPP: 0,
335    SHARED_LIB: 1
336  }
337
338  /**
339   * Parser for dynamic code optimization state.
340   */
341  static parseState(s) {
342    switch (s) {
343      case '':
344        return this.CodeState.COMPILED;
345      case '~':
346        return this.CodeState.IGNITION;
347      case '^':
348        return this.CodeState.BASELINE;
349      case '+':
350        return this.CodeState.TURBOPROP;
351      case '*':
352        return this.CodeState.TURBOFAN;
353    }
354    throw new Error(`unknown code state: ${s}`);
355  }
356
357  static getKindFromState(state) {
358    if (state === this.CodeState.COMPILED) {
359      return "Builtin";
360    } else if (state === this.CodeState.IGNITION) {
361      return "Unopt";
362    } else if (state === this.CodeState.BASELINE) {
363      return "Baseline";
364    } else if (state === this.CodeState.TURBOPROP) {
365      return "Turboprop";
366    } else if (state === this.CodeState.TURBOFAN) {
367      return "Opt";
368    }
369    throw new Error(`unknown code state: ${state}`);
370  }
371
372  static vmStateString(state) {
373    switch (state) {
374      case this.VMState.JS:
375        return 'JS';
376      case this.VMState.GC:
377        return 'GC';
378      case this.VMState.PARSER:
379        return 'Parse';
380      case this.VMState.BYTECODE_COMPILER:
381        return 'Compile Bytecode';
382      case this.VMState.COMPILER:
383        return 'Compile';
384      case this.VMState.OTHER:
385        return 'Other';
386      case this.VMState.EXTERNAL:
387        return 'External';
388      case this.VMState.IDLE:
389        return 'Idle';
390    }
391    return 'unknown';
392  }
393
394  /**
395   * Called whenever the specified operation has failed finding a function
396   * containing the specified address. Should be overriden by subclasses.
397   * See the Profile.Operation enum for the list of
398   * possible operations.
399   *
400   * @param {number} operation Operation.
401   * @param {number} addr Address of the unknown code.
402   * @param {number} opt_stackPos If an unknown address is encountered
403   *     during stack strace processing, specifies a position of the frame
404   *     containing the address.
405   */
406  handleUnknownCode(operation, addr, opt_stackPos) { }
407
408  /**
409   * Registers a library.
410   *
411   * @param {string} name Code entry name.
412   * @param {number} startAddr Starting address.
413   * @param {number} endAddr Ending address.
414   */
415  addLibrary(name, startAddr, endAddr) {
416    const entry = new CodeEntry(endAddr - startAddr, name, 'SHARED_LIB');
417    this.codeMap_.addLibrary(startAddr, entry);
418    return entry;
419  }
420
421  /**
422   * Registers statically compiled code entry.
423   *
424   * @param {string} name Code entry name.
425   * @param {number} startAddr Starting address.
426   * @param {number} endAddr Ending address.
427   */
428  addStaticCode(name, startAddr, endAddr) {
429    const entry = new CodeEntry(endAddr - startAddr, name, 'CPP');
430    this.codeMap_.addStaticCode(startAddr, entry);
431    return entry;
432  }
433
434  /**
435   * Registers dynamic (JIT-compiled) code entry.
436   *
437   * @param {string} type Code entry type.
438   * @param {string} name Code entry name.
439   * @param {number} start Starting address.
440   * @param {number} size Code entry size.
441   */
442  addCode(type, name, timestamp, start, size) {
443    const entry = new DynamicCodeEntry(size, type, name);
444    this.codeMap_.addCode(start, entry);
445    return entry;
446  }
447
448  /**
449   * Registers dynamic (JIT-compiled) code entry.
450   *
451   * @param {string} type Code entry type.
452   * @param {string} name Code entry name.
453   * @param {number} start Starting address.
454   * @param {number} size Code entry size.
455   * @param {number} funcAddr Shared function object address.
456   * @param {Profile.CodeState} state Optimization state.
457   */
458  addFuncCode(type, name, timestamp, start, size, funcAddr, state) {
459    // As code and functions are in the same address space,
460    // it is safe to put them in a single code map.
461    let func = this.codeMap_.findDynamicEntryByStartAddress(funcAddr);
462    if (!func) {
463      func = new FunctionEntry(name);
464      this.codeMap_.addCode(funcAddr, func);
465    } else if (func.name !== name) {
466      // Function object has been overwritten with a new one.
467      func.name = name;
468    }
469    let entry = this.codeMap_.findDynamicEntryByStartAddress(start);
470    if (entry) {
471      if (entry.size === size && entry.func === func) {
472        // Entry state has changed.
473        entry.state = state;
474      } else {
475        this.codeMap_.deleteCode(start);
476        entry = null;
477      }
478    }
479    if (!entry) {
480      entry = new DynamicFuncCodeEntry(size, type, func, state);
481      this.codeMap_.addCode(start, entry);
482    }
483    return entry;
484  }
485
486  /**
487   * Reports about moving of a dynamic code entry.
488   *
489   * @param {number} from Current code entry address.
490   * @param {number} to New code entry address.
491   */
492  moveCode(from, to) {
493    try {
494      this.codeMap_.moveCode(from, to);
495    } catch (e) {
496      this.handleUnknownCode(Profile.Operation.MOVE, from);
497    }
498  }
499
500  deoptCode(timestamp, code, inliningId, scriptOffset, bailoutType,
501    sourcePositionText, deoptReasonText) {
502  }
503
504  /**
505   * Reports about deletion of a dynamic code entry.
506   *
507   * @param {number} start Starting address.
508   */
509  deleteCode(start) {
510    try {
511      this.codeMap_.deleteCode(start);
512    } catch (e) {
513      this.handleUnknownCode(Profile.Operation.DELETE, start);
514    }
515  }
516
517  /**
518   * Adds source positions for given code.
519   */
520  addSourcePositions(start, scriptId, startPos, endPos, sourcePositionTable,
521        inliningPositions, inlinedFunctions) {
522    const script = this.getOrCreateScript(scriptId);
523    const entry = this.codeMap_.findDynamicEntryByStartAddress(start);
524    if (!entry) return;
525    // Resolve the inlined functions list.
526    if (inlinedFunctions.length > 0) {
527      inlinedFunctions = inlinedFunctions.substring(1).split("S");
528      for (let i = 0; i < inlinedFunctions.length; i++) {
529        const funcAddr = parseInt(inlinedFunctions[i]);
530        const func = this.codeMap_.findDynamicEntryByStartAddress(funcAddr);
531        if (!func || func.funcId === undefined) {
532          // TODO: fix
533          console.warn(`Could not find function ${inlinedFunctions[i]}`);
534          inlinedFunctions[i] = null;
535        } else {
536          inlinedFunctions[i] = func.funcId;
537        }
538      }
539    } else {
540      inlinedFunctions = [];
541    }
542
543    this.getOrCreateSourceInfo(entry).setSourcePositionInfo(
544      script, startPos, endPos, sourcePositionTable, inliningPositions,
545      inlinedFunctions);
546  }
547
548  addDisassemble(start, kind, disassemble) {
549    const entry = this.codeMap_.findDynamicEntryByStartAddress(start);
550    if (entry) this.getOrCreateSourceInfo(entry).setDisassemble(disassemble);
551    return entry;
552  }
553
554  getOrCreateSourceInfo(entry) {
555    return entry.source ?? (entry.source = new SourceInfo());
556  }
557
558  addScriptSource(id, url, source) {
559    const script = this.getOrCreateScript(id);
560    script.update(url, source);
561    this.urlToScript_.set(url, script);
562  }
563
564  getOrCreateScript(id) {
565    let script = this.scripts_[id];
566    if (!script) {
567      script = new Script(id);
568      this.scripts_[id] = script;
569    }
570    return script;
571  }
572
573  getScript(url) {
574    return this.urlToScript_.get(url);
575  }
576
577  /**
578   * Reports about moving of a dynamic code entry.
579   *
580   * @param {number} from Current code entry address.
581   * @param {number} to New code entry address.
582   */
583  moveFunc(from, to) {
584    if (this.codeMap_.findDynamicEntryByStartAddress(from)) {
585      this.codeMap_.moveCode(from, to);
586    }
587  }
588
589  /**
590   * Retrieves a code entry by an address.
591   *
592   * @param {number} addr Entry address.
593   */
594  findEntry(addr) {
595    return this.codeMap_.findEntry(addr);
596  }
597
598  /**
599   * Records a tick event. Stack must contain a sequence of
600   * addresses starting with the program counter value.
601   *
602   * @param {Array<number>} stack Stack sample.
603   */
604  recordTick(time_ns, vmState, stack) {
605    const {nameStack, entryStack} = this.resolveAndFilterFuncs_(stack);
606    this.bottomUpTree_.addPath(nameStack);
607    nameStack.reverse();
608    this.topDownTree_.addPath(nameStack);
609    return entryStack;
610  }
611
612  /**
613   * Translates addresses into function names and filters unneeded
614   * functions.
615   *
616   * @param {Array<number>} stack Stack sample.
617   */
618  resolveAndFilterFuncs_(stack) {
619    const nameStack = [];
620    const entryStack = [];
621    let last_seen_c_function = '';
622    let look_for_first_c_function = false;
623    for (let i = 0; i < stack.length; ++i) {
624      const pc = stack[i];
625      const entry = this.codeMap_.findEntry(pc);
626      if (entry) {
627        entryStack.push(entry);
628        const name = entry.getName();
629        if (i === 0 && (entry.type === 'CPP' || entry.type === 'SHARED_LIB')) {
630          look_for_first_c_function = true;
631        }
632        if (look_for_first_c_function && entry.type === 'CPP') {
633          last_seen_c_function = name;
634        }
635        if (!this.skipThisFunction(name)) {
636          nameStack.push(name);
637        }
638      } else {
639        this.handleUnknownCode(Profile.Operation.TICK, pc, i);
640        if (i === 0) nameStack.push("UNKNOWN");
641        entryStack.push(pc);
642      }
643      if (look_for_first_c_function && i > 0 &&
644          (!entry || entry.type !== 'CPP') && last_seen_c_function !== '') {
645        if (this.c_entries_[last_seen_c_function] === undefined) {
646          this.c_entries_[last_seen_c_function] = 0;
647        }
648        this.c_entries_[last_seen_c_function]++;
649        look_for_first_c_function = false;  // Found it, we're done.
650      }
651    }
652    return {nameStack, entryStack};
653  }
654
655  /**
656   * Performs a BF traversal of the top down call graph.
657   *
658   * @param {function(CallTreeNode)} f Visitor function.
659   */
660  traverseTopDownTree(f) {
661    this.topDownTree_.traverse(f);
662  }
663
664  /**
665   * Performs a BF traversal of the bottom up call graph.
666   *
667   * @param {function(CallTreeNode)} f Visitor function.
668   */
669  traverseBottomUpTree(f) {
670    this.bottomUpTree_.traverse(f);
671  }
672
673  /**
674   * Calculates a top down profile for a node with the specified label.
675   * If no name specified, returns the whole top down calls tree.
676   *
677   * @param {string} opt_label Node label.
678   */
679  getTopDownProfile(opt_label) {
680    return this.getTreeProfile_(this.topDownTree_, opt_label);
681  }
682
683  /**
684   * Calculates a bottom up profile for a node with the specified label.
685   * If no name specified, returns the whole bottom up calls tree.
686   *
687   * @param {string} opt_label Node label.
688   */
689  getBottomUpProfile(opt_label) {
690    return this.getTreeProfile_(this.bottomUpTree_, opt_label);
691  }
692
693  /**
694   * Helper function for calculating a tree profile.
695   *
696   * @param {Profile.CallTree} tree Call tree.
697   * @param {string} opt_label Node label.
698   */
699  getTreeProfile_(tree, opt_label) {
700    if (!opt_label) {
701      tree.computeTotalWeights();
702      return tree;
703    } else {
704      const subTree = tree.cloneSubtree(opt_label);
705      subTree.computeTotalWeights();
706      return subTree;
707    }
708  }
709
710  /**
711   * Calculates a flat profile of callees starting from a node with
712   * the specified label. If no name specified, starts from the root.
713   *
714   * @param {string} opt_label Starting node label.
715   */
716  getFlatProfile(opt_label) {
717    const counters = new CallTree();
718    const rootLabel = opt_label || CallTree.ROOT_NODE_LABEL;
719    const precs = {};
720    precs[rootLabel] = 0;
721    const root = counters.findOrAddChild(rootLabel);
722
723    this.topDownTree_.computeTotalWeights();
724    this.topDownTree_.traverseInDepth(
725      function onEnter(node) {
726        if (!(node.label in precs)) {
727          precs[node.label] = 0;
728        }
729        const nodeLabelIsRootLabel = node.label == rootLabel;
730        if (nodeLabelIsRootLabel || precs[rootLabel] > 0) {
731          if (precs[rootLabel] == 0) {
732            root.selfWeight += node.selfWeight;
733            root.totalWeight += node.totalWeight;
734          } else {
735            const rec = root.findOrAddChild(node.label);
736            rec.selfWeight += node.selfWeight;
737            if (nodeLabelIsRootLabel || precs[node.label] == 0) {
738              rec.totalWeight += node.totalWeight;
739            }
740          }
741          precs[node.label]++;
742        }
743      },
744      function onExit(node) {
745        if (node.label == rootLabel || precs[rootLabel] > 0) {
746          precs[node.label]--;
747        }
748      },
749      null);
750
751    if (!opt_label) {
752      // If we have created a flat profile for the whole program, we don't
753      // need an explicit root in it. Thus, replace the counters tree
754      // root with the node corresponding to the whole program.
755      counters.root_ = root;
756    } else {
757      // Propagate weights so percents can be calculated correctly.
758      counters.getRoot().selfWeight = root.selfWeight;
759      counters.getRoot().totalWeight = root.totalWeight;
760    }
761    return counters;
762  }
763
764  getCEntryProfile() {
765    const result = [new CEntryNode("TOTAL", 0)];
766    let total_ticks = 0;
767    for (let f in this.c_entries_) {
768      const ticks = this.c_entries_[f];
769      total_ticks += ticks;
770      result.push(new CEntryNode(f, ticks));
771    }
772    result[0].ticks = total_ticks;  // Sorting will keep this at index 0.
773    result.sort((n1, n2) => n2.ticks - n1.ticks || (n2.name < n1.name ? -1 : 1));
774    return result;
775  }
776
777
778  /**
779   * Cleans up function entries that are not referenced by code entries.
780   */
781  cleanUpFuncEntries() {
782    const referencedFuncEntries = [];
783    const entries = this.codeMap_.getAllDynamicEntriesWithAddresses();
784    for (let i = 0, l = entries.length; i < l; ++i) {
785      if (entries[i][1].constructor === FunctionEntry) {
786        entries[i][1].used = false;
787      }
788    }
789    for (let i = 0, l = entries.length; i < l; ++i) {
790      if ("func" in entries[i][1]) {
791        entries[i][1].func.used = true;
792      }
793    }
794    for (let i = 0, l = entries.length; i < l; ++i) {
795      if (entries[i][1].constructor === FunctionEntry &&
796        !entries[i][1].used) {
797        this.codeMap_.deleteCode(entries[i][0]);
798      }
799    }
800  }
801}
802
803class CEntryNode {
804  constructor(name, ticks) {
805    this.name = name;
806    this.ticks = ticks;
807  }
808}
809
810
811/**
812 * Creates a dynamic code entry.
813 *
814 * @param {number} size Code size.
815 * @param {string} type Code type.
816 * @param {string} name Function name.
817 * @constructor
818 */
819class DynamicCodeEntry extends CodeEntry {
820  constructor(size, type, name) {
821    super(size, name, type);
822  }
823
824  getName() {
825    return this.type + ': ' + this.name;
826  }
827
828  /**
829   * Returns raw node name (without type decoration).
830   */
831  getRawName() {
832    return this.name;
833  }
834
835  isJSFunction() {
836    return false;
837  }
838
839  toString() {
840    return this.getName() + ': ' + this.size.toString(16);
841  }
842}
843
844
845/**
846 * Creates a dynamic code entry.
847 *
848 * @param {number} size Code size.
849 * @param {string} type Code type.
850 * @param {FunctionEntry} func Shared function entry.
851 * @param {Profile.CodeState} state Code optimization state.
852 * @constructor
853 */
854class DynamicFuncCodeEntry extends CodeEntry {
855  constructor(size, type, func, state) {
856    super(size, '', type);
857    this.func = func;
858    func.addDynamicCode(this);
859    this.state = state;
860  }
861
862  get functionName() {
863    return this.func.functionName;
864  }
865
866  getSourceCode() {
867    return this.source?.getSourceCode();
868  }
869
870  static STATE_PREFIX = ["", "~", "^", "-", "+", "*"];
871  getState() {
872    return DynamicFuncCodeEntry.STATE_PREFIX[this.state];
873  }
874
875  getName() {
876    const name = this.func.getName();
877    return this.type + ': ' + this.getState() + name;
878  }
879
880  /**
881   * Returns raw node name (without type decoration).
882   */
883  getRawName() {
884    return this.func.getName();
885  }
886
887  isJSFunction() {
888    return true;
889  }
890
891  toString() {
892    return this.getName() + ': ' + this.size.toString(16);
893  }
894}
895
896/**
897 * Creates a shared function object entry.
898 *
899 * @param {string} name Function name.
900 * @constructor
901 */
902class FunctionEntry extends CodeEntry {
903
904  // Contains the list of generated code for this function.
905  _codeEntries = new Set();
906
907  constructor(name) {
908    super(0, name);
909    const index = name.lastIndexOf(' ');
910    this.functionName = 1 <= index ? name.substring(0, index) : '<anonymous>';
911  }
912
913  addDynamicCode(code) {
914    if (code.func != this) {
915      throw new Error("Adding dynamic code to wrong function");
916    }
917    this._codeEntries.add(code);
918  }
919
920  getSourceCode() {
921    // All code entries should map to the same source positions.
922    return this._codeEntries.values().next().value.getSourceCode();
923  }
924
925  get codeEntries() {
926    return this._codeEntries;
927  }
928
929  /**
930   * Returns node name.
931   */
932  getName() {
933    let name = this.name;
934    if (name.length == 0) {
935      return '<anonymous>';
936    } else if (name.charAt(0) == ' ') {
937      // An anonymous function with location: " aaa.js:10".
938      return `<anonymous>${name}`;
939    }
940    return name;
941  }
942}
943
944/**
945 * Constructs a call graph.
946 *
947 * @constructor
948 */
949class CallTree {
950  root_ = new CallTreeNode(CallTree.ROOT_NODE_LABEL);
951  totalsComputed_ = false;
952
953  /**
954   * The label of the root node.
955   */
956  static ROOT_NODE_LABEL = '';
957
958  /**
959   * Returns the tree root.
960   */
961  getRoot() {
962    return this.root_;
963  }
964
965  /**
966   * Adds the specified call path, constructing nodes as necessary.
967   *
968   * @param {Array<string>} path Call path.
969   */
970  addPath(path) {
971    if (path.length == 0) {
972      return;
973    }
974    let curr = this.root_;
975    for (let i = 0; i < path.length; ++i) {
976      curr = curr.findOrAddChild(path[i]);
977    }
978    curr.selfWeight++;
979    this.totalsComputed_ = false;
980  }
981
982  /**
983   * Finds an immediate child of the specified parent with the specified
984   * label, creates a child node if necessary. If a parent node isn't
985   * specified, uses tree root.
986   *
987   * @param {string} label Child node label.
988   */
989  findOrAddChild(label) {
990    return this.root_.findOrAddChild(label);
991  }
992
993  /**
994   * Creates a subtree by cloning and merging all subtrees rooted at nodes
995   * with a given label. E.g. cloning the following call tree on label 'A'
996   * will give the following result:
997   *
998   *           <A>--<B>                                     <B>
999   *          /                                            /
1000   *     <root>             == clone on 'A' ==>  <root>--<A>
1001   *          \                                            \
1002   *           <C>--<A>--<D>                                <D>
1003   *
1004   * And <A>'s selfWeight will be the sum of selfWeights of <A>'s from the
1005   * source call tree.
1006   *
1007   * @param {string} label The label of the new root node.
1008   */
1009  cloneSubtree(label) {
1010    const subTree = new CallTree();
1011    this.traverse((node, parent) => {
1012      if (!parent && node.label != label) {
1013        return null;
1014      }
1015      const child = (parent ? parent : subTree).findOrAddChild(node.label);
1016      child.selfWeight += node.selfWeight;
1017      return child;
1018    });
1019    return subTree;
1020  }
1021
1022  /**
1023   * Computes total weights in the call graph.
1024   */
1025  computeTotalWeights() {
1026    if (this.totalsComputed_) return;
1027    this.root_.computeTotalWeight();
1028    this.totalsComputed_ = true;
1029  }
1030
1031  /**
1032   * Traverses the call graph in preorder. This function can be used for
1033   * building optionally modified tree clones. This is the boilerplate code
1034   * for this scenario:
1035   *
1036   * callTree.traverse(function(node, parentClone) {
1037   *   var nodeClone = cloneNode(node);
1038   *   if (parentClone)
1039   *     parentClone.addChild(nodeClone);
1040   *   return nodeClone;
1041   * });
1042   *
1043   * @param {function(CallTreeNode, *)} f Visitor function.
1044   *    The second parameter is the result of calling 'f' on the parent node.
1045   */
1046  traverse(f) {
1047    const pairsToProcess = new ConsArray();
1048    pairsToProcess.concat([{ node: this.root_, param: null }]);
1049    while (!pairsToProcess.atEnd()) {
1050      const pair = pairsToProcess.next();
1051      const node = pair.node;
1052      const newParam = f(node, pair.param);
1053      const morePairsToProcess = [];
1054      node.forEachChild((child) => {
1055        morePairsToProcess.push({ node: child, param: newParam });
1056      });
1057      pairsToProcess.concat(morePairsToProcess);
1058    }
1059  }
1060
1061  /**
1062   * Performs an indepth call graph traversal.
1063   *
1064   * @param {function(CallTreeNode)} enter A function called
1065   *     prior to visiting node's children.
1066   * @param {function(CallTreeNode)} exit A function called
1067   *     after visiting node's children.
1068   */
1069  traverseInDepth(enter, exit) {
1070    function traverse(node) {
1071      enter(node);
1072      node.forEachChild(traverse);
1073      exit(node);
1074    }
1075    traverse(this.root_);
1076  }
1077}
1078
1079
1080/**
1081 * Constructs a call graph node.
1082 *
1083 * @param {string} label Node label.
1084 * @param {CallTreeNode} opt_parent Node parent.
1085 */
1086class CallTreeNode {
1087  /**
1088   * Node self weight (how many times this node was the last node in
1089   * a call path).
1090   * @type {number}
1091   */
1092  selfWeight = 0;
1093
1094  /**
1095   * Node total weight (includes weights of all children).
1096   * @type {number}
1097   */
1098  totalWeight = 0;
1099  children = {};
1100
1101  constructor(label, opt_parent) {
1102    this.label = label;
1103    this.parent = opt_parent;
1104  }
1105
1106
1107  /**
1108   * Adds a child node.
1109   *
1110   * @param {string} label Child node label.
1111   */
1112  addChild(label) {
1113    const child = new CallTreeNode(label, this);
1114    this.children[label] = child;
1115    return child;
1116  }
1117
1118  /**
1119   * Computes node's total weight.
1120   */
1121  computeTotalWeight() {
1122    let totalWeight = this.selfWeight;
1123    this.forEachChild(function (child) {
1124      totalWeight += child.computeTotalWeight();
1125    });
1126    return this.totalWeight = totalWeight;
1127  }
1128
1129  /**
1130   * Returns all node's children as an array.
1131   */
1132  exportChildren() {
1133    const result = [];
1134    this.forEachChild(function (node) { result.push(node); });
1135    return result;
1136  }
1137
1138  /**
1139   * Finds an immediate child with the specified label.
1140   *
1141   * @param {string} label Child node label.
1142   */
1143  findChild(label) {
1144    return this.children[label] || null;
1145  }
1146
1147  /**
1148   * Finds an immediate child with the specified label, creates a child
1149   * node if necessary.
1150   *
1151   * @param {string} label Child node label.
1152   */
1153  findOrAddChild(label) {
1154    return this.findChild(label) || this.addChild(label);
1155  }
1156
1157  /**
1158   * Calls the specified function for every child.
1159   *
1160   * @param {function(CallTreeNode)} f Visitor function.
1161   */
1162  forEachChild(f) {
1163    for (let c in this.children) {
1164      f(this.children[c]);
1165    }
1166  }
1167
1168  /**
1169   * Walks up from the current node up to the call tree root.
1170   *
1171   * @param {function(CallTreeNode)} f Visitor function.
1172   */
1173  walkUpToRoot(f) {
1174    for (let curr = this; curr != null; curr = curr.parent) {
1175      f(curr);
1176    }
1177  }
1178
1179  /**
1180   * Tries to find a node with the specified path.
1181   *
1182   * @param {Array<string>} labels The path.
1183   * @param {function(CallTreeNode)} opt_f Visitor function.
1184   */
1185  descendToChild(labels, opt_f) {
1186    let curr = this;
1187    for (let pos = 0; pos < labels.length && curr != null; pos++) {
1188      const child = curr.findChild(labels[pos]);
1189      if (opt_f) {
1190        opt_f(child, pos);
1191      }
1192      curr = child;
1193    }
1194    return curr;
1195  }
1196}
1197
1198export function JsonProfile() {
1199  this.codeMap_ = new CodeMap();
1200  this.codeEntries_ = [];
1201  this.functionEntries_ = [];
1202  this.ticks_ = [];
1203  this.scripts_ = [];
1204}
1205
1206JsonProfile.prototype.addLibrary = function (
1207  name, startAddr, endAddr) {
1208  const entry = new CodeEntry(
1209    endAddr - startAddr, name, 'SHARED_LIB');
1210  this.codeMap_.addLibrary(startAddr, entry);
1211
1212  entry.codeId = this.codeEntries_.length;
1213  this.codeEntries_.push({ name: entry.name, type: entry.type });
1214  return entry;
1215};
1216
1217JsonProfile.prototype.addStaticCode = function (
1218  name, startAddr, endAddr) {
1219  const entry = new CodeEntry(
1220    endAddr - startAddr, name, 'CPP');
1221  this.codeMap_.addStaticCode(startAddr, entry);
1222
1223  entry.codeId = this.codeEntries_.length;
1224  this.codeEntries_.push({ name: entry.name, type: entry.type });
1225  return entry;
1226};
1227
1228JsonProfile.prototype.addCode = function (
1229  kind, name, timestamp, start, size) {
1230  let codeId = this.codeEntries_.length;
1231  // Find out if we have a static code entry for the code. If yes, we will
1232  // make sure it is written to the JSON file just once.
1233  let staticEntry = this.codeMap_.findAddress(start);
1234  if (staticEntry && staticEntry.entry.type === 'CPP') {
1235    codeId = staticEntry.entry.codeId;
1236  }
1237
1238  const entry = new CodeEntry(size, name, 'CODE');
1239  this.codeMap_.addCode(start, entry);
1240
1241  entry.codeId = codeId;
1242  this.codeEntries_[codeId] = {
1243    name: entry.name,
1244    timestamp: timestamp,
1245    type: entry.type,
1246    kind: kind,
1247  };
1248
1249  return entry;
1250};
1251
1252JsonProfile.prototype.addFuncCode = function (
1253  kind, name, timestamp, start, size, funcAddr, state) {
1254  // As code and functions are in the same address space,
1255  // it is safe to put them in a single code map.
1256  let func = this.codeMap_.findDynamicEntryByStartAddress(funcAddr);
1257  if (!func) {
1258    func = new CodeEntry(0, name, 'SFI');
1259    this.codeMap_.addCode(funcAddr, func);
1260
1261    func.funcId = this.functionEntries_.length;
1262    this.functionEntries_.push({ name, codes: [] });
1263  } else if (func.name !== name) {
1264    // Function object has been overwritten with a new one.
1265    func.name = name;
1266
1267    func.funcId = this.functionEntries_.length;
1268    this.functionEntries_.push({ name, codes: [] });
1269  }
1270  // TODO(jarin): Insert the code object into the SFI's code list.
1271  let entry = this.codeMap_.findDynamicEntryByStartAddress(start);
1272  if (entry) {
1273    if (entry.size === size && entry.func === func) {
1274      // Entry state has changed.
1275      entry.state = state;
1276    } else {
1277      this.codeMap_.deleteCode(start);
1278      entry = null;
1279    }
1280  }
1281  if (!entry) {
1282    entry = new CodeEntry(size, name, 'JS');
1283    this.codeMap_.addCode(start, entry);
1284
1285    entry.codeId = this.codeEntries_.length;
1286
1287    this.functionEntries_[func.funcId].codes.push(entry.codeId);
1288
1289    kind = Profile.getKindFromState(state);
1290
1291    this.codeEntries_.push({
1292      name: entry.name,
1293      type: entry.type,
1294      kind: kind,
1295      func: func.funcId,
1296      tm: timestamp,
1297    });
1298  }
1299  return entry;
1300};
1301
1302JsonProfile.prototype.moveCode = function (from, to) {
1303  try {
1304    this.codeMap_.moveCode(from, to);
1305  } catch (e) {
1306    printErr(`Move: unknown source ${from}`);
1307  }
1308};
1309
1310JsonProfile.prototype.addSourcePositions = function (
1311  start, script, startPos, endPos, sourcePositions, inliningPositions,
1312  inlinedFunctions) {
1313  const entry = this.codeMap_.findDynamicEntryByStartAddress(start);
1314  if (!entry) return;
1315  const codeId = entry.codeId;
1316
1317  // Resolve the inlined functions list.
1318  if (inlinedFunctions.length > 0) {
1319    inlinedFunctions = inlinedFunctions.substring(1).split("S");
1320    for (let i = 0; i < inlinedFunctions.length; i++) {
1321      const funcAddr = parseInt(inlinedFunctions[i]);
1322      const func = this.codeMap_.findDynamicEntryByStartAddress(funcAddr);
1323      if (!func || func.funcId === undefined) {
1324        printErr(`Could not find function ${inlinedFunctions[i]}`);
1325        inlinedFunctions[i] = null;
1326      } else {
1327        inlinedFunctions[i] = func.funcId;
1328      }
1329    }
1330  } else {
1331    inlinedFunctions = [];
1332  }
1333
1334  this.codeEntries_[entry.codeId].source = {
1335    script: script,
1336    start: startPos,
1337    end: endPos,
1338    positions: sourcePositions,
1339    inlined: inliningPositions,
1340    fns: inlinedFunctions
1341  };
1342};
1343
1344JsonProfile.prototype.addScriptSource = function (id, url, source) {
1345  const script = new Script(id);
1346  script.update(url, source);
1347  this.scripts_[id] = script;
1348};
1349
1350JsonProfile.prototype.deoptCode = function (
1351  timestamp, code, inliningId, scriptOffset, bailoutType,
1352  sourcePositionText, deoptReasonText) {
1353  let entry = this.codeMap_.findDynamicEntryByStartAddress(code);
1354  if (entry) {
1355    let codeId = entry.codeId;
1356    if (!this.codeEntries_[codeId].deopt) {
1357      // Only add the deopt if there was no deopt before.
1358      // The subsequent deoptimizations should be lazy deopts for
1359      // other on-stack activations.
1360      this.codeEntries_[codeId].deopt = {
1361        tm: timestamp,
1362        inliningId: inliningId,
1363        scriptOffset: scriptOffset,
1364        posText: sourcePositionText,
1365        reason: deoptReasonText,
1366        bailoutType: bailoutType,
1367      };
1368    }
1369  }
1370};
1371
1372JsonProfile.prototype.deleteCode = function (start) {
1373  try {
1374    this.codeMap_.deleteCode(start);
1375  } catch (e) {
1376    printErr(`Delete: unknown address ${start}`);
1377  }
1378};
1379
1380JsonProfile.prototype.moveFunc = function (from, to) {
1381  if (this.codeMap_.findDynamicEntryByStartAddress(from)) {
1382    this.codeMap_.moveCode(from, to);
1383  }
1384};
1385
1386JsonProfile.prototype.findEntry = function (addr) {
1387  return this.codeMap_.findEntry(addr);
1388};
1389
1390JsonProfile.prototype.recordTick = function (time_ns, vmState, stack) {
1391  // TODO(jarin) Resolve the frame-less case (when top of stack is
1392  // known code).
1393  const processedStack = [];
1394  for (let i = 0; i < stack.length; i++) {
1395    const resolved = this.codeMap_.findAddress(stack[i]);
1396    if (resolved) {
1397      processedStack.push(resolved.entry.codeId, resolved.offset);
1398    } else {
1399      processedStack.push(-1, stack[i]);
1400    }
1401  }
1402  this.ticks_.push({ tm: time_ns, vm: vmState, s: processedStack });
1403};
1404
1405function writeJson(s) {
1406  write(JSON.stringify(s, null, 2));
1407}
1408
1409JsonProfile.prototype.writeJson = function () {
1410  // Write out the JSON in a partially manual way to avoid creating too-large
1411  // strings in one JSON.stringify call when there are a lot of ticks.
1412  write('{\n')
1413
1414  write('  "code": ');
1415  writeJson(this.codeEntries_);
1416  write(',\n');
1417
1418  write('  "functions": ');
1419  writeJson(this.functionEntries_);
1420  write(',\n');
1421
1422  write('  "ticks": [\n');
1423  for (let i = 0; i < this.ticks_.length; i++) {
1424    write('    ');
1425    writeJson(this.ticks_[i]);
1426    if (i < this.ticks_.length - 1) {
1427      write(',\n');
1428    } else {
1429      write('\n');
1430    }
1431  }
1432  write('  ],\n');
1433
1434  write('  "scripts": ');
1435  writeJson(this.scripts_);
1436
1437  write('}\n');
1438};
1439