From 5d309ff52cd399a6b71968a6b9a70c8ac0b98981 Mon Sep 17 00:00:00 2001 From: Joel Kronqvist Date: Sat, 5 Mar 2022 19:02:27 +0200 Subject: Added node_modules for the updating to work properly. --- .../@bcoe/v8-coverage/dist/lib/_src/ascii.ts | 146 +++++++++ .../@bcoe/v8-coverage/dist/lib/_src/clone.ts | 70 +++++ .../@bcoe/v8-coverage/dist/lib/_src/compare.ts | 40 +++ .../@bcoe/v8-coverage/dist/lib/_src/index.ts | 6 + .../@bcoe/v8-coverage/dist/lib/_src/merge.ts | 343 +++++++++++++++++++++ .../@bcoe/v8-coverage/dist/lib/_src/normalize.ts | 84 +++++ .../@bcoe/v8-coverage/dist/lib/_src/range-tree.ts | 156 ++++++++++ .../@bcoe/v8-coverage/dist/lib/_src/types.ts | 26 ++ 8 files changed, 871 insertions(+) create mode 100644 node_modules/@bcoe/v8-coverage/dist/lib/_src/ascii.ts create mode 100644 node_modules/@bcoe/v8-coverage/dist/lib/_src/clone.ts create mode 100644 node_modules/@bcoe/v8-coverage/dist/lib/_src/compare.ts create mode 100644 node_modules/@bcoe/v8-coverage/dist/lib/_src/index.ts create mode 100644 node_modules/@bcoe/v8-coverage/dist/lib/_src/merge.ts create mode 100644 node_modules/@bcoe/v8-coverage/dist/lib/_src/normalize.ts create mode 100644 node_modules/@bcoe/v8-coverage/dist/lib/_src/range-tree.ts create mode 100644 node_modules/@bcoe/v8-coverage/dist/lib/_src/types.ts (limited to 'node_modules/@bcoe/v8-coverage/dist/lib/_src') diff --git a/node_modules/@bcoe/v8-coverage/dist/lib/_src/ascii.ts b/node_modules/@bcoe/v8-coverage/dist/lib/_src/ascii.ts new file mode 100644 index 0000000..5a52b91 --- /dev/null +++ b/node_modules/@bcoe/v8-coverage/dist/lib/_src/ascii.ts @@ -0,0 +1,146 @@ +import { compareRangeCovs } from "./compare"; +import { RangeCov } from "./types"; + +interface ReadonlyRangeTree { + readonly start: number; + readonly end: number; + readonly count: number; + readonly children: ReadonlyRangeTree[]; +} + +export function emitForest(trees: ReadonlyArray): string { + return emitForestLines(trees).join("\n"); +} + +export function emitForestLines(trees: ReadonlyArray): string[] { + const colMap: Map = getColMap(trees); + const header: string = emitOffsets(colMap); + return [header, ...trees.map(tree => emitTree(tree, colMap).join("\n"))]; +} + +function getColMap(trees: Iterable): Map { + const eventSet: Set = new Set(); + for (const tree of trees) { + const stack: ReadonlyRangeTree[] = [tree]; + while (stack.length > 0) { + const cur: ReadonlyRangeTree = stack.pop()!; + eventSet.add(cur.start); + eventSet.add(cur.end); + for (const child of cur.children) { + stack.push(child); + } + } + } + const events: number[] = [...eventSet]; + events.sort((a, b) => a - b); + let maxDigits: number = 1; + for (const event of events) { + maxDigits = Math.max(maxDigits, event.toString(10).length); + } + const colWidth: number = maxDigits + 3; + const colMap: Map = new Map(); + for (const [i, event] of events.entries()) { + colMap.set(event, i * colWidth); + } + return colMap; +} + +function emitTree(tree: ReadonlyRangeTree, colMap: Map): string[] { + const layers: ReadonlyRangeTree[][] = []; + let nextLayer: ReadonlyRangeTree[] = [tree]; + while (nextLayer.length > 0) { + const layer: ReadonlyRangeTree[] = 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)); +} + +export function parseFunctionRanges(text: string, offsetMap: Map): RangeCov[] { + const result: RangeCov[] = []; + 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: ReadonlyRangeTree[], colMap: Map): string { + const line: string[] = []; + let curIdx: number = 0; + for (const {start, end, count} of layer) { + const startIdx: number = colMap.get(start)!; + const endIdx: number = 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: string, offsetMap: Map): RangeCov[] { + const result: RangeCov[] = []; + const regex: RegExp = /\[(\d+)-*\)/gs; + while (true) { + const match: RegExpMatchArray | null = regex.exec(text); + if (match === null) { + break; + } + const startIdx: number = match.index!; + const endIdx: number = startIdx + match[0].length; + const count: number = parseInt(match[1], 10); + const startOffset: number | undefined = offsetMap.get(startIdx); + const endOffset: number | undefined = 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: number, len: number): string { + const rangeStart: string = `[${count.toString(10)}`; + const rangeEnd: string = ")"; + const hyphensLen: number = len - (rangeStart.length + rangeEnd.length); + const hyphens: string = "-".repeat(Math.max(0, hyphensLen)); + return `${rangeStart}${hyphens}${rangeEnd}`; +} + +function emitOffsets(colMap: Map): string { + let line: string = ""; + for (const [event, col] of colMap) { + if (line.length < col) { + line += " ".repeat(col - line.length); + } + line += event.toString(10); + } + return line; +} + +export function parseOffsets(text: string): Map { + const result: Map = new Map(); + const regex: RegExp = /\d+/gs; + while (true) { + const match: RegExpExecArray | null = regex.exec(text); + if (match === null) { + break; + } + result.set(match.index, parseInt(match[0], 10)); + } + return result; +} diff --git a/node_modules/@bcoe/v8-coverage/dist/lib/_src/clone.ts b/node_modules/@bcoe/v8-coverage/dist/lib/_src/clone.ts new file mode 100644 index 0000000..1a91019 --- /dev/null +++ b/node_modules/@bcoe/v8-coverage/dist/lib/_src/clone.ts @@ -0,0 +1,70 @@ +import { FunctionCov, ProcessCov, RangeCov, ScriptCov } from "./types"; + +/** + * Creates a deep copy of a process coverage. + * + * @param processCov Process coverage to clone. + * @return Cloned process coverage. + */ +export function cloneProcessCov(processCov: Readonly): ProcessCov { + const result: ScriptCov[] = []; + 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. + */ +export function cloneScriptCov(scriptCov: Readonly): ScriptCov { + const functions: FunctionCov[] = []; + 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. + */ +export function cloneFunctionCov(functionCov: Readonly): FunctionCov { + const ranges: RangeCov[] = []; + 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. + */ +export function cloneRangeCov(rangeCov: Readonly): RangeCov { + return { + startOffset: rangeCov.startOffset, + endOffset: rangeCov.endOffset, + count: rangeCov.count, + }; +} diff --git a/node_modules/@bcoe/v8-coverage/dist/lib/_src/compare.ts b/node_modules/@bcoe/v8-coverage/dist/lib/_src/compare.ts new file mode 100644 index 0000000..8f5614c --- /dev/null +++ b/node_modules/@bcoe/v8-coverage/dist/lib/_src/compare.ts @@ -0,0 +1,40 @@ +import { FunctionCov, RangeCov, ScriptCov } from "./types"; + +/** + * Compares two script coverages. + * + * The result corresponds to the comparison of their `url` value (alphabetical sort). + */ +export function compareScriptCovs(a: Readonly, b: Readonly): number { + 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. + */ +export function compareFunctionCovs(a: Readonly, b: Readonly): number { + 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. + */ +export function compareRangeCovs(a: Readonly, b: Readonly): number { + if (a.startOffset !== b.startOffset) { + return a.startOffset - b.startOffset; + } else { + return b.endOffset - a.endOffset; + } +} diff --git a/node_modules/@bcoe/v8-coverage/dist/lib/_src/index.ts b/node_modules/@bcoe/v8-coverage/dist/lib/_src/index.ts new file mode 100644 index 0000000..f92bdf3 --- /dev/null +++ b/node_modules/@bcoe/v8-coverage/dist/lib/_src/index.ts @@ -0,0 +1,6 @@ +export { emitForest, emitForestLines, parseFunctionRanges, parseOffsets } from "./ascii"; +export { cloneFunctionCov, cloneProcessCov, cloneScriptCov, cloneRangeCov } from "./clone"; +export { compareScriptCovs, compareFunctionCovs, compareRangeCovs } from "./compare"; +export { mergeFunctionCovs, mergeProcessCovs, mergeScriptCovs } from "./merge"; +export { RangeTree } from "./range-tree"; +export { ProcessCov, ScriptCov, FunctionCov, RangeCov } from "./types"; diff --git a/node_modules/@bcoe/v8-coverage/dist/lib/_src/merge.ts b/node_modules/@bcoe/v8-coverage/dist/lib/_src/merge.ts new file mode 100644 index 0000000..64d1918 --- /dev/null +++ b/node_modules/@bcoe/v8-coverage/dist/lib/_src/merge.ts @@ -0,0 +1,343 @@ +import { + deepNormalizeScriptCov, + normalizeFunctionCov, + normalizeProcessCov, + normalizeRangeTree, + normalizeScriptCov, +} from "./normalize"; +import { RangeTree } from "./range-tree"; +import { FunctionCov, ProcessCov, Range, RangeCov, ScriptCov } from "./types"; + +/** + * 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. + */ +export function mergeProcessCovs(processCovs: ReadonlyArray): ProcessCov { + if (processCovs.length === 0) { + return {result: []}; + } + + const urlToScripts: Map = new Map(); + for (const processCov of processCovs) { + for (const scriptCov of processCov.result) { + let scriptCovs: ScriptCov[] | undefined = urlToScripts.get(scriptCov.url); + if (scriptCovs === undefined) { + scriptCovs = []; + urlToScripts.set(scriptCov.url, scriptCovs); + } + scriptCovs.push(scriptCov); + } + } + + const result: ScriptCov[] = []; + for (const scripts of urlToScripts.values()) { + // assert: `scripts.length > 0` + result.push(mergeScriptCovs(scripts)!); + } + const merged: ProcessCov = {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. + */ +export function mergeScriptCovs(scriptCovs: ReadonlyArray): ScriptCov | undefined { + if (scriptCovs.length === 0) { + return undefined; + } else if (scriptCovs.length === 1) { + const merged: ScriptCov = scriptCovs[0]; + deepNormalizeScriptCov(merged); + return merged; + } + + const first: ScriptCov = scriptCovs[0]; + const scriptId: string = first.scriptId; + const url: string = first.url; + + const rangeToFuncs: Map = new Map(); + for (const scriptCov of scriptCovs) { + for (const funcCov of scriptCov.functions) { + const rootRange: string = stringifyFunctionRootRange(funcCov); + let funcCovs: FunctionCov[] | undefined = 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: FunctionCov[] = []; + for (const funcCovs of rangeToFuncs.values()) { + // assert: `funcCovs.length > 0` + functions.push(mergeFunctionCovs(funcCovs)!); + } + + const merged: ScriptCov = {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: Readonly): string { + const rootRange: RangeCov = 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. + */ +export function mergeFunctionCovs(funcCovs: ReadonlyArray): FunctionCov | undefined { + if (funcCovs.length === 0) { + return undefined; + } else if (funcCovs.length === 1) { + const merged: FunctionCov = funcCovs[0]; + normalizeFunctionCov(merged); + return merged; + } + + const functionName: string = funcCovs[0].functionName; + + const trees: RangeTree[] = []; + 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: RangeTree = mergeRangeTrees(trees)!; + normalizeRangeTree(mergedTree); + const ranges: RangeCov[] = mergedTree.toRanges(); + const isBlockCoverage: boolean = !(ranges.length === 1 && ranges[0].count === 0); + + const merged: FunctionCov = {functionName, ranges, isBlockCoverage}; + // assert: `merged` is normalized + return merged; +} + +/** + * @precondition Same `start` and `end` for all the trees + */ +function mergeRangeTrees(trees: ReadonlyArray): RangeTree | undefined { + if (trees.length <= 1) { + return trees[0]; + } + const first: RangeTree = trees[0]; + let delta: number = 0; + for (const tree of trees) { + delta += tree.delta; + } + const children: RangeTree[] = mergeRangeTreeChildren(trees); + return new RangeTree(first.start, first.end, delta, children); +} + +class RangeTreeWithParent { + readonly parentIndex: number; + readonly tree: RangeTree; + + constructor(parentIndex: number, tree: RangeTree) { + this.parentIndex = parentIndex; + this.tree = tree; + } +} + +class StartEvent { + readonly offset: number; + readonly trees: RangeTreeWithParent[]; + + constructor(offset: number, trees: RangeTreeWithParent[]) { + this.offset = offset; + this.trees = trees; + } + + static compare(a: StartEvent, b: StartEvent): number { + return a.offset - b.offset; + } +} + +class StartEventQueue { + private readonly queue: StartEvent[]; + private nextIndex: number; + private pendingOffset: number; + private pendingTrees: RangeTreeWithParent[] | undefined; + + private constructor(queue: StartEvent[]) { + this.queue = queue; + this.nextIndex = 0; + this.pendingOffset = 0; + this.pendingTrees = undefined; + } + + static fromParentTrees(parentTrees: ReadonlyArray): StartEventQueue { + const startToTrees: Map = new Map(); + for (const [parentIndex, parentTree] of parentTrees.entries()) { + for (const child of parentTree.children) { + let trees: RangeTreeWithParent[] | undefined = startToTrees.get(child.start); + if (trees === undefined) { + trees = []; + startToTrees.set(child.start, trees); + } + trees.push(new RangeTreeWithParent(parentIndex, child)); + } + } + const queue: StartEvent[] = []; + for (const [startOffset, trees] of startToTrees) { + queue.push(new StartEvent(startOffset, trees)); + } + queue.sort(StartEvent.compare); + return new StartEventQueue(queue); + } + + setPendingOffset(offset: number): void { + this.pendingOffset = offset; + } + + pushPendingTree(tree: RangeTreeWithParent): void { + if (this.pendingTrees === undefined) { + this.pendingTrees = []; + } + this.pendingTrees.push(tree); + } + + next(): StartEvent | undefined { + const pendingTrees: RangeTreeWithParent[] | undefined = this.pendingTrees; + const nextEvent: StartEvent | undefined = 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: ReadonlyArray): RangeTree[] { + const result: RangeTree[] = []; + const startEventQueue: StartEventQueue = StartEventQueue.fromParentTrees(parentTrees); + const parentToNested: Map = new Map(); + let openRange: Range | undefined; + + while (true) { + const event: StartEvent | undefined = 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: number = 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: RangeTree = 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: Map, parentIndex: number, tree: RangeTree): void { + let nested: RangeTree[] | undefined = parentToNested.get(parentIndex); + if (nested === undefined) { + nested = []; + parentToNested.set(parentIndex, nested); + } + nested.push(tree); +} + +function nextChild(openRange: Range, parentToNested: Map): RangeTree { + const matchingTrees: RangeTree[] = []; + + 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)!; +} diff --git a/node_modules/@bcoe/v8-coverage/dist/lib/_src/normalize.ts b/node_modules/@bcoe/v8-coverage/dist/lib/_src/normalize.ts new file mode 100644 index 0000000..0269116 --- /dev/null +++ b/node_modules/@bcoe/v8-coverage/dist/lib/_src/normalize.ts @@ -0,0 +1,84 @@ +import { compareFunctionCovs, compareRangeCovs, compareScriptCovs } from "./compare"; +import { RangeTree } from "./range-tree"; +import { FunctionCov, ProcessCov, ScriptCov } from "./types"; + +/** + * 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. + */ +export function normalizeProcessCov(processCov: ProcessCov): void { + 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. + */ +export function deepNormalizeProcessCov(processCov: ProcessCov): void { + 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. + */ +export function normalizeScriptCov(scriptCov: ScriptCov): void { + 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. + */ +export function deepNormalizeScriptCov(scriptCov: ScriptCov): void { + 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. + */ +export function normalizeFunctionCov(funcCov: FunctionCov): void { + funcCov.ranges.sort(compareRangeCovs); + const tree: RangeTree = RangeTree.fromSortedRanges(funcCov.ranges)!; + normalizeRangeTree(tree); + funcCov.ranges = tree.toRanges(); +} + +/** + * @internal + */ +export function normalizeRangeTree(tree: RangeTree): void { + tree.normalize(); +} diff --git a/node_modules/@bcoe/v8-coverage/dist/lib/_src/range-tree.ts b/node_modules/@bcoe/v8-coverage/dist/lib/_src/range-tree.ts new file mode 100644 index 0000000..941ec82 --- /dev/null +++ b/node_modules/@bcoe/v8-coverage/dist/lib/_src/range-tree.ts @@ -0,0 +1,156 @@ +import { RangeCov } from "./types"; + +export class RangeTree { + start: number; + end: number; + delta: number; + children: RangeTree[]; + + constructor( + start: number, + end: number, + delta: number, + children: RangeTree[], + ) { + this.start = start; + this.end = end; + this.delta = delta; + this.children = children; + } + + /** + * @precodition `ranges` are well-formed and pre-order sorted + */ + static fromSortedRanges(ranges: ReadonlyArray): RangeTree | undefined { + let root: RangeTree | undefined; + // Stack of parent trees and parent counts. + const stack: [RangeTree, number][] = []; + for (const range of ranges) { + const node: RangeTree = new RangeTree(range.startOffset, range.endOffset, range.count, []); + if (root === undefined) { + root = node; + stack.push([node, range.count]); + continue; + } + let parent: RangeTree; + let parentCount: number; + while (true) { + [parent, parentCount] = stack[stack.length - 1]; + // assert: `top !== undefined` (the ranges are sorted) + if (range.startOffset < parent.end) { + break; + } else { + stack.pop(); + } + } + node.delta -= parentCount; + parent.children.push(node); + stack.push([node, range.count]); + } + return root; + } + + normalize(): void { + const children: RangeTree[] = []; + let curEnd: number; + let head: RangeTree | undefined; + const tail: RangeTree[] = []; + 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: RangeTree = 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(): void { + 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: number): RangeTree { + let leftChildLen: number = this.children.length; + let mid: RangeTree | undefined; + + // TODO(perf): Binary search (check overhead) + for (let i: number = 0; i < this.children.length; i++) { + const child: RangeTree = 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: number = this.children.length - leftChildLen; + const rightChildren: RangeTree[] = this.children.splice(leftChildLen, rightLen); + if (mid !== undefined) { + rightChildren.unshift(mid); + } + const result: RangeTree = 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(): RangeCov[] { + const ranges: RangeCov[] = []; + // Stack of parent trees and counts. + const stack: [RangeTree, number][] = [[this, 0]]; + while (stack.length > 0) { + const [cur, parentCount]: [RangeTree, number] = stack.pop()!; + const count: number = parentCount + cur.delta; + ranges.push({startOffset: cur.start, endOffset: cur.end, count}); + for (let i: number = cur.children.length - 1; i >= 0; i--) { + stack.push([cur.children[i], count]); + } + } + return ranges; + } +} diff --git a/node_modules/@bcoe/v8-coverage/dist/lib/_src/types.ts b/node_modules/@bcoe/v8-coverage/dist/lib/_src/types.ts new file mode 100644 index 0000000..cc2cfc5 --- /dev/null +++ b/node_modules/@bcoe/v8-coverage/dist/lib/_src/types.ts @@ -0,0 +1,26 @@ +export interface ProcessCov { + result: ScriptCov[]; +} + +export interface ScriptCov { + scriptId: string; + url: string; + functions: FunctionCov[]; +} + +export interface FunctionCov { + functionName: string; + ranges: RangeCov[]; + isBlockCoverage: boolean; +} + +export interface Range { + readonly start: number; + readonly end: number; +} + +export interface RangeCov { + startOffset: number; + endOffset: number; + count: number; +} -- cgit v1.2.3