diff options
Diffstat (limited to 'vanilla/node_modules/@bcoe/v8-coverage/src/lib')
7 files changed, 911 insertions, 0 deletions
diff --git a/vanilla/node_modules/@bcoe/v8-coverage/src/lib/ascii.js b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/ascii.js new file mode 100644 index 0000000..f0700ca --- /dev/null +++ b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/ascii.js @@ -0,0 +1,145 @@ +const { compareRangeCovs } = require("./compare"); + +function emitForest(trees) { + return emitForestLines(trees).join("\n"); +} + +function emitForestLines(trees) { + const colMap = getColMap(trees); + const header = emitOffsets(colMap); + return [header, ...trees.map((tree) => emitTree(tree, colMap).join("\n"))]; +} + +function getColMap(trees) { + const eventSet = new Set(); + for (const tree of trees) { + const stack = [tree]; + while (stack.length > 0) { + const cur = stack.pop(); + eventSet.add(cur.start); + eventSet.add(cur.end); + for (const child of cur.children) { + stack.push(child); + } + } + } + const events = [...eventSet]; + events.sort((a, b) => a - b); + let maxDigits = 1; + for (const event of events) { + maxDigits = Math.max(maxDigits, event.toString(10).length); + } + const colWidth = maxDigits + 3; + const colMap = new Map(); + for (const [i, event] of events.entries()) { + colMap.set(event, i * colWidth); + } + return colMap; +} + +function emitTree(tree, colMap) { + const layers = []; + let nextLayer = [tree]; + while (nextLayer.length > 0) { + const layer = nextLayer; + layers.push(layer); + nextLayer = []; + for (const node of layer) { + for (const child of node.children) { + nextLayer.push(child); + } + } + } + return layers.map((layer) => emitTreeLayer(layer, colMap)); +} + +function parseFunctionRanges(text, offsetMap) { + const result = []; + for (const line of text.split("\n")) { + for (const range of parseTreeLayer(line, offsetMap)) { + result.push(range); + } + } + result.sort(compareRangeCovs); + return result; +} + +/** + * + * @param layer Sorted list of disjoint trees. + * @param colMap + */ +function emitTreeLayer(layer, colMap) { + const line = []; + let curIdx = 0; + for (const { start, end, count } of layer) { + const startIdx = colMap.get(start); + const endIdx = colMap.get(end); + if (startIdx > curIdx) { + line.push(" ".repeat(startIdx - curIdx)); + } + line.push(emitRange(count, endIdx - startIdx)); + curIdx = endIdx; + } + return line.join(""); +} + +function parseTreeLayer(text, offsetMap) { + const result = []; + const regex = /\[(\d+)-*\)/gs; + while (true) { + const match = regex.exec(text); + if (match === null) { + break; + } + const startIdx = match.index; + const endIdx = startIdx + match[0].length; + const count = parseInt(match[1], 10); + const startOffset = offsetMap.get(startIdx); + const endOffset = offsetMap.get(endIdx); + if (startOffset === undefined || endOffset === undefined) { + throw new Error(`Invalid offsets for: ${JSON.stringify(text)}`); + } + result.push({ startOffset, endOffset, count }); + } + return result; +} + +function emitRange(count, len) { + const rangeStart = `[${count.toString(10)}`; + const rangeEnd = ")"; + const hyphensLen = len - (rangeStart.length + rangeEnd.length); + const hyphens = "-".repeat(Math.max(0, hyphensLen)); + return `${rangeStart}${hyphens}${rangeEnd}`; +} + +function emitOffsets(colMap) { + let line = ""; + for (const [event, col] of colMap) { + if (line.length < col) { + line += " ".repeat(col - line.length); + } + line += event.toString(10); + } + return line; +} + +function parseOffsets(text) { + const result = new Map(); + const regex = /\d+/gs; + while (true) { + const match = regex.exec(text); + if (match === null) { + break; + } + result.set(match.index, parseInt(match[0], 10)); + } + return result; +} + +module.exports = { + emitForest, + emitForestLines, + parseFunctionRanges, + parseOffsets, +}; diff --git a/vanilla/node_modules/@bcoe/v8-coverage/src/lib/clone.js b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/clone.js new file mode 100644 index 0000000..44c5e27 --- /dev/null +++ b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/clone.js @@ -0,0 +1,75 @@ +/** + * Creates a deep copy of a process coverage. + * + * @param processCov Process coverage to clone. + * @return Cloned process coverage. + */ +function cloneProcessCov(processCov) { + const result = []; + for (const scriptCov of processCov.result) { + result.push(cloneScriptCov(scriptCov)); + } + + return { + result, + }; +} + +/** + * Creates a deep copy of a script coverage. + * + * @param scriptCov Script coverage to clone. + * @return Cloned script coverage. + */ +function cloneScriptCov(scriptCov) { + const functions = []; + for (const functionCov of scriptCov.functions) { + functions.push(cloneFunctionCov(functionCov)); + } + + return { + scriptId: scriptCov.scriptId, + url: scriptCov.url, + functions, + }; +} + +/** + * Creates a deep copy of a function coverage. + * + * @param functionCov Function coverage to clone. + * @return Cloned function coverage. + */ +function cloneFunctionCov(functionCov) { + const ranges = []; + for (const rangeCov of functionCov.ranges) { + ranges.push(cloneRangeCov(rangeCov)); + } + + return { + functionName: functionCov.functionName, + ranges, + isBlockCoverage: functionCov.isBlockCoverage, + }; +} + +/** + * Creates a deep copy of a function coverage. + * + * @param rangeCov Range coverage to clone. + * @return Cloned range coverage. + */ +function cloneRangeCov(rangeCov) { + return { + startOffset: rangeCov.startOffset, + endOffset: rangeCov.endOffset, + count: rangeCov.count, + }; +} + +module.exports = { + cloneProcessCov, + cloneScriptCov, + cloneFunctionCov, + cloneRangeCov, +}; diff --git a/vanilla/node_modules/@bcoe/v8-coverage/src/lib/compare.js b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/compare.js new file mode 100644 index 0000000..d887018 --- /dev/null +++ b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/compare.js @@ -0,0 +1,44 @@ +/** + * Compares two script coverages. + * + * The result corresponds to the comparison of their `url` value (alphabetical sort). + */ +function compareScriptCovs(a, b) { + if (a.url === b.url) { + return 0; + } else if (a.url < b.url) { + return -1; + } else { + return 1; + } +} + +/** + * Compares two function coverages. + * + * The result corresponds to the comparison of the root ranges. + */ +function compareFunctionCovs(a, b) { + return compareRangeCovs(a.ranges[0], b.ranges[0]); +} + +/** + * Compares two range coverages. + * + * The ranges are first ordered by ascending `startOffset` and then by + * descending `endOffset`. + * This corresponds to a pre-order tree traversal. + */ +function compareRangeCovs(a, b) { + if (a.startOffset !== b.startOffset) { + return a.startOffset - b.startOffset; + } else { + return b.endOffset - a.endOffset; + } +} + +module.exports = { + compareScriptCovs, + compareFunctionCovs, + compareRangeCovs, +}; diff --git a/vanilla/node_modules/@bcoe/v8-coverage/src/lib/index.js b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/index.js new file mode 100644 index 0000000..0429ad5 --- /dev/null +++ b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/index.js @@ -0,0 +1,41 @@ +const { + emitForest, + emitForestLines, + parseFunctionRanges, + parseOffsets, +} = require("./ascii"); +const { + cloneFunctionCov, + cloneProcessCov, + cloneScriptCov, + cloneRangeCov, +} = require("./clone"); +const { + compareScriptCovs, + compareFunctionCovs, + compareRangeCovs, +} = require("./compare"); +const { + mergeFunctionCovs, + mergeProcessCovs, + mergeScriptCovs, +} = require("./merge"); +const { RangeTree } = require("./range-tree"); + +module.exports = { + emitForest, + emitForestLines, + parseFunctionRanges, + parseOffsets, + cloneFunctionCov, + cloneProcessCov, + cloneScriptCov, + cloneRangeCov, + compareScriptCovs, + compareFunctionCovs, + compareRangeCovs, + mergeFunctionCovs, + mergeProcessCovs, + mergeScriptCovs, + RangeTree, +}; diff --git a/vanilla/node_modules/@bcoe/v8-coverage/src/lib/merge.js b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/merge.js new file mode 100644 index 0000000..1f3d915 --- /dev/null +++ b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/merge.js @@ -0,0 +1,353 @@ +const { + deepNormalizeScriptCov, + normalizeFunctionCov, + normalizeProcessCov, + normalizeRangeTree, + normalizeScriptCov, +} = require("./normalize"); +const { RangeTree } = require("./range-tree"); + +/** + * Merges a list of process coverages. + * + * The result is normalized. + * The input values may be mutated, it is not safe to use them after passing + * them to this function. + * The computation is synchronous. + * + * @param processCovs Process coverages to merge. + * @return Merged process coverage. + */ +function mergeProcessCovs(processCovs) { + if (processCovs.length === 0) { + return { result: [] }; + } + + const urlToScripts = new Map(); + for (const processCov of processCovs) { + for (const scriptCov of processCov.result) { + let scriptCovs = urlToScripts.get(scriptCov.url); + if (scriptCovs === undefined) { + scriptCovs = []; + urlToScripts.set(scriptCov.url, scriptCovs); + } + scriptCovs.push(scriptCov); + } + } + + const result = []; + for (const scripts of urlToScripts.values()) { + // assert: `scripts.length > 0` + result.push(mergeScriptCovs(scripts)); + } + const merged = { result }; + + normalizeProcessCov(merged); + return merged; +} + +/** + * Merges a list of matching script coverages. + * + * Scripts are matching if they have the same `url`. + * The result is normalized. + * The input values may be mutated, it is not safe to use them after passing + * them to this function. + * The computation is synchronous. + * + * @param scriptCovs Process coverages to merge. + * @return Merged script coverage, or `undefined` if the input list was empty. + */ +function mergeScriptCovs(scriptCovs) { + if (scriptCovs.length === 0) { + return undefined; + } else if (scriptCovs.length === 1) { + const merged = scriptCovs[0]; + deepNormalizeScriptCov(merged); + return merged; + } + + const first = scriptCovs[0]; + const scriptId = first.scriptId; + const url = first.url; + + const rangeToFuncs = new Map(); + for (const scriptCov of scriptCovs) { + for (const funcCov of scriptCov.functions) { + const rootRange = stringifyFunctionRootRange(funcCov); + let funcCovs = rangeToFuncs.get(rootRange); + + if ( + funcCovs === undefined || + // if the entry in rangeToFuncs is function-level granularity and + // the new coverage is block-level, prefer block-level. + (!funcCovs[0].isBlockCoverage && funcCov.isBlockCoverage) + ) { + funcCovs = []; + rangeToFuncs.set(rootRange, funcCovs); + } else if (funcCovs[0].isBlockCoverage && !funcCov.isBlockCoverage) { + // if the entry in rangeToFuncs is block-level granularity, we should + // not append function level granularity. + continue; + } + funcCovs.push(funcCov); + } + } + + const functions = []; + for (const funcCovs of rangeToFuncs.values()) { + // assert: `funcCovs.length > 0` + functions.push(mergeFunctionCovs(funcCovs)); + } + + const merged = { scriptId, url, functions }; + normalizeScriptCov(merged); + return merged; +} + +/** + * Returns a string representation of the root range of the function. + * + * This string can be used to match function with same root range. + * The string is derived from the start and end offsets of the root range of + * the function. + * This assumes that `ranges` is non-empty (true for valid function coverages). + * + * @param funcCov Function coverage with the range to stringify + * @internal + */ +function stringifyFunctionRootRange(funcCov) { + const rootRange = funcCov.ranges[0]; + return `${rootRange.startOffset.toString(10)};${rootRange.endOffset.toString(10)}`; +} + +/** + * Merges a list of matching function coverages. + * + * Functions are matching if their root ranges have the same span. + * The result is normalized. + * The input values may be mutated, it is not safe to use them after passing + * them to this function. + * The computation is synchronous. + * + * @param funcCovs Function coverages to merge. + * @return Merged function coverage, or `undefined` if the input list was empty. + */ +function mergeFunctionCovs(funcCovs) { + if (funcCovs.length === 0) { + return undefined; + } else if (funcCovs.length === 1) { + const merged = funcCovs[0]; + normalizeFunctionCov(merged); + return merged; + } + + const functionName = funcCovs[0].functionName; + + const trees = []; + for (const funcCov of funcCovs) { + // assert: `fn.ranges.length > 0` + // assert: `fn.ranges` is sorted + trees.push(RangeTree.fromSortedRanges(funcCov.ranges)); + } + + // assert: `trees.length > 0` + const mergedTree = mergeRangeTrees(trees); + normalizeRangeTree(mergedTree); + const ranges = mergedTree.toRanges(); + const isBlockCoverage = !(ranges.length === 1 && ranges[0].count === 0); + + const merged = { functionName, ranges, isBlockCoverage }; + // assert: `merged` is normalized + return merged; +} + +/** + * @precondition Same `start` and `end` for all the trees + */ +function mergeRangeTrees(trees) { + if (trees.length <= 1) { + return trees[0]; + } + const first = trees[0]; + let delta = 0; + for (const tree of trees) { + delta += tree.delta; + } + const children = mergeRangeTreeChildren(trees); + return new RangeTree(first.start, first.end, delta, children); +} + +class RangeTreeWithParent { + parentIndex; + tree; + + constructor(parentIndex, tree) { + this.parentIndex = parentIndex; + this.tree = tree; + } +} + +class StartEvent { + offset; + trees; + + constructor(offset, trees) { + this.offset = offset; + this.trees = trees; + } + + static compare(a, b) { + return a.offset - b.offset; + } +} + +class StartEventQueue { + queue; + nextIndex; + pendingOffset; + pendingTrees; + + constructor(queue) { + this.queue = queue; + this.nextIndex = 0; + this.pendingOffset = 0; + this.pendingTrees = undefined; + } + + static fromParentTrees(parentTrees) { + const startToTrees = new Map(); + for (const [parentIndex, parentTree] of parentTrees.entries()) { + for (const child of parentTree.children) { + let trees = startToTrees.get(child.start); + if (trees === undefined) { + trees = []; + startToTrees.set(child.start, trees); + } + trees.push(new RangeTreeWithParent(parentIndex, child)); + } + } + const queue = []; + for (const [startOffset, trees] of startToTrees) { + queue.push(new StartEvent(startOffset, trees)); + } + queue.sort(StartEvent.compare); + return new StartEventQueue(queue); + } + + setPendingOffset(offset) { + this.pendingOffset = offset; + } + + pushPendingTree(tree) { + if (this.pendingTrees === undefined) { + this.pendingTrees = []; + } + this.pendingTrees.push(tree); + } + + next() { + const pendingTrees = this.pendingTrees; + const nextEvent = this.queue[this.nextIndex]; + if (pendingTrees === undefined) { + this.nextIndex++; + return nextEvent; + } else if (nextEvent === undefined) { + this.pendingTrees = undefined; + return new StartEvent(this.pendingOffset, pendingTrees); + } else { + if (this.pendingOffset < nextEvent.offset) { + this.pendingTrees = undefined; + return new StartEvent(this.pendingOffset, pendingTrees); + } else { + if (this.pendingOffset === nextEvent.offset) { + this.pendingTrees = undefined; + for (const tree of pendingTrees) { + nextEvent.trees.push(tree); + } + } + this.nextIndex++; + return nextEvent; + } + } + } +} + +function mergeRangeTreeChildren(parentTrees) { + const result = []; + const startEventQueue = StartEventQueue.fromParentTrees(parentTrees); + const parentToNested = new Map(); + let openRange; + + while (true) { + const event = startEventQueue.next(); + if (event === undefined) { + break; + } + + if (openRange !== undefined && openRange.end <= event.offset) { + result.push(nextChild(openRange, parentToNested)); + openRange = undefined; + } + + if (openRange === undefined) { + let openRangeEnd = event.offset + 1; + for (const { parentIndex, tree } of event.trees) { + openRangeEnd = Math.max(openRangeEnd, tree.end); + insertChild(parentToNested, parentIndex, tree); + } + startEventQueue.setPendingOffset(openRangeEnd); + openRange = { start: event.offset, end: openRangeEnd }; + } else { + for (const { parentIndex, tree } of event.trees) { + if (tree.end > openRange.end) { + const right = tree.split(openRange.end); + startEventQueue.pushPendingTree( + new RangeTreeWithParent(parentIndex, right), + ); + } + insertChild(parentToNested, parentIndex, tree); + } + } + } + if (openRange !== undefined) { + result.push(nextChild(openRange, parentToNested)); + } + + return result; +} + +function insertChild(parentToNested, parentIndex, tree) { + let nested = parentToNested.get(parentIndex); + if (nested === undefined) { + nested = []; + parentToNested.set(parentIndex, nested); + } + nested.push(tree); +} + +function nextChild(openRange, parentToNested) { + const matchingTrees = []; + + for (const nested of parentToNested.values()) { + if ( + nested.length === 1 && + nested[0].start === openRange.start && + nested[0].end === openRange.end + ) { + matchingTrees.push(nested[0]); + } else { + matchingTrees.push( + new RangeTree(openRange.start, openRange.end, 0, nested), + ); + } + } + parentToNested.clear(); + return mergeRangeTrees(matchingTrees); +} + +module.exports = { + mergeProcessCovs, + mergeScriptCovs, + mergeFunctionCovs, +}; diff --git a/vanilla/node_modules/@bcoe/v8-coverage/src/lib/normalize.js b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/normalize.js new file mode 100644 index 0000000..130e9b8 --- /dev/null +++ b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/normalize.js @@ -0,0 +1,96 @@ +const { + compareFunctionCovs, + compareRangeCovs, + compareScriptCovs, +} = require("./compare"); +const { RangeTree } = require("./range-tree"); + +/** + * Normalizes a process coverage. + * + * Sorts the scripts alphabetically by `url`. + * Reassigns script ids: the script at index `0` receives `"0"`, the script at + * index `1` receives `"1"` etc. + * This does not normalize the script coverages. + * + * @param processCov Process coverage to normalize. + */ +function normalizeProcessCov(processCov) { + processCov.result.sort(compareScriptCovs); + for (const [scriptId, scriptCov] of processCov.result.entries()) { + scriptCov.scriptId = scriptId.toString(10); + } +} + +/** + * Normalizes a process coverage deeply. + * + * Normalizes the script coverages deeply, then normalizes the process coverage + * itself. + * + * @param processCov Process coverage to normalize. + */ +function deepNormalizeProcessCov(processCov) { + for (const scriptCov of processCov.result) { + deepNormalizeScriptCov(scriptCov); + } + normalizeProcessCov(processCov); +} + +/** + * Normalizes a script coverage. + * + * Sorts the function by root range (pre-order sort). + * This does not normalize the function coverages. + * + * @param scriptCov Script coverage to normalize. + */ +function normalizeScriptCov(scriptCov) { + scriptCov.functions.sort(compareFunctionCovs); +} + +/** + * Normalizes a script coverage deeply. + * + * Normalizes the function coverages deeply, then normalizes the script coverage + * itself. + * + * @param scriptCov Script coverage to normalize. + */ +function deepNormalizeScriptCov(scriptCov) { + for (const funcCov of scriptCov.functions) { + normalizeFunctionCov(funcCov); + } + normalizeScriptCov(scriptCov); +} + +/** + * Normalizes a function coverage. + * + * Sorts the ranges (pre-order sort). + * TODO: Tree-based normalization of the ranges. + * + * @param funcCov Function coverage to normalize. + */ +function normalizeFunctionCov(funcCov) { + funcCov.ranges.sort(compareRangeCovs); + const tree = RangeTree.fromSortedRanges(funcCov.ranges); + normalizeRangeTree(tree); + funcCov.ranges = tree.toRanges(); +} + +/** + * @internal + */ +function normalizeRangeTree(tree) { + tree.normalize(); +} + +module.exports = { + normalizeProcessCov, + deepNormalizeProcessCov, + normalizeScriptCov, + deepNormalizeScriptCov, + normalizeFunctionCov, + normalizeRangeTree, +}; diff --git a/vanilla/node_modules/@bcoe/v8-coverage/src/lib/range-tree.js b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/range-tree.js new file mode 100644 index 0000000..2bd456f --- /dev/null +++ b/vanilla/node_modules/@bcoe/v8-coverage/src/lib/range-tree.js @@ -0,0 +1,157 @@ +class RangeTree { + start; + end; + delta; + children; + + constructor(start, end, delta, children) { + this.start = start; + this.end = end; + this.delta = delta; + this.children = children; + } + + /** + * @precodition `ranges` are well-formed and pre-order sorted + */ + static fromSortedRanges(ranges) { + let root; + // Stack of parent trees and parent counts. + const stack = []; + for (const range of ranges) { + const node = new RangeTree( + range.startOffset, + range.endOffset, + range.count, + [], + ); + if (root === undefined) { + root = node; + stack.push([node, range.count]); + continue; + } + let parent; + let parentCount; + while (true) { + [parent, parentCount] = stack[stack.length - 1]; + // assert: `top !== undefined` (the ranges are sorted) + if (range.startOffset < parent.end) { + break; + } else { + stack.pop(); + } + + if (stack.length === 0) { + break; + } + } + node.delta -= parentCount; + parent.children.push(node); + stack.push([node, range.count]); + } + return root; + } + + normalize() { + const children = []; + let curEnd; + let head; + const tail = []; + for (const child of this.children) { + if (head === undefined) { + head = child; + } else if (child.delta === head.delta && child.start === curEnd) { + tail.push(child); + } else { + endChain(); + head = child; + } + curEnd = child.end; + } + if (head !== undefined) { + endChain(); + } + + if (children.length === 1) { + const child = children[0]; + if (child.start === this.start && child.end === this.end) { + this.delta += child.delta; + this.children = child.children; + // `.lazyCount` is zero for both (both are after normalization) + return; + } + } + + this.children = children; + + function endChain() { + if (tail.length !== 0) { + head.end = tail[tail.length - 1].end; + for (const tailTree of tail) { + for (const subChild of tailTree.children) { + subChild.delta += tailTree.delta - head.delta; + head.children.push(subChild); + } + } + tail.length = 0; + } + head.normalize(); + children.push(head); + } + } + + /** + * @precondition `tree.start < value && value < tree.end` + * @return RangeTree Right part + */ + split(value) { + let leftChildLen = this.children.length; + let mid; + + // TODO(perf): Binary search (check overhead) + for (let i = 0; i < this.children.length; i++) { + const child = this.children[i]; + if (child.start < value && value < child.end) { + mid = child.split(value); + leftChildLen = i + 1; + break; + } else if (child.start >= value) { + leftChildLen = i; + break; + } + } + + const rightLen = this.children.length - leftChildLen; + const rightChildren = this.children.splice(leftChildLen, rightLen); + if (mid !== undefined) { + rightChildren.unshift(mid); + } + const result = new RangeTree(value, this.end, this.delta, rightChildren); + this.end = value; + return result; + } + + /** + * Get the range coverages corresponding to the tree. + * + * The ranges are pre-order sorted. + */ + toRanges() { + const ranges = []; + // Stack of parent trees and counts. + const stack = [[this, 0]]; + while (stack.length > 0) { + const [cur, parentCount] = stack.pop(); + const count = parentCount + cur.delta; + ranges.push({ startOffset: cur.start, endOffset: cur.end, count }); + for (let i = cur.children.length - 1; i >= 0; i--) { + stack.push([cur.children[i], count]); + } + } + return ranges; + } +} + +module.exports = { + RangeTree, +}; |