forked from M3-Academy/challenge-algorithms-v2.0
303 lines
36 KiB
JavaScript
303 lines
36 KiB
JavaScript
|
"use strict";
|
||
|
|
Object.defineProperty(exports, "__esModule", { value: true });
|
||
|
|
const normalize_1 = require("./normalize");
|
||
|
|
const range_tree_1 = 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 };
|
||
|
|
normalize_1.normalizeProcessCov(merged);
|
||
|
|
return merged;
|
||
|
|
}
|
||
|
|
exports.mergeProcessCovs = mergeProcessCovs;
|
||
|
|
/**
|
||
|
|
* 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];
|
||
|
|
normalize_1.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 };
|
||
|
|
normalize_1.normalizeScriptCov(merged);
|
||
|
|
return merged;
|
||
|
|
}
|
||
|
|
exports.mergeScriptCovs = mergeScriptCovs;
|
||
|
|
/**
|
||
|
|
* 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];
|
||
|
|
normalize_1.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(range_tree_1.RangeTree.fromSortedRanges(funcCov.ranges));
|
||
|
|
}
|
||
|
|
// assert: `trees.length > 0`
|
||
|
|
const mergedTree = mergeRangeTrees(trees);
|
||
|
|
normalize_1.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;
|
||
|
|
}
|
||
|
|
exports.mergeFunctionCovs = mergeFunctionCovs;
|
||
|
|
/**
|
||
|
|
* @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 range_tree_1.RangeTree(first.start, first.end, delta, children);
|
||
|
|
}
|
||
|
|
class RangeTreeWithParent {
|
||
|
|
constructor(parentIndex, tree) {
|
||
|
|
this.parentIndex = parentIndex;
|
||
|
|
this.tree = tree;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
class StartEvent {
|
||
|
|
constructor(offset, trees) {
|
||
|
|
this.offset = offset;
|
||
|
|
this.trees = trees;
|
||
|
|
}
|
||
|
|
static compare(a, b) {
|
||
|
|
return a.offset - b.offset;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
class StartEventQueue {
|
||
|
|
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 range_tree_1.RangeTree(openRange.start, openRange.end, 0, nested));
|
||
|
|
}
|
||
|
|
}
|
||
|
|
parentToNested.clear();
|
||
|
|
return mergeRangeTrees(matchingTrees);
|
||
|
|
}
|
||
|
|
|
||
|
|
//# sourceMappingURL=data:application/json;charset=utf8;base64,eyJ2ZXJzaW9uIjozLCJzb3VyY2VzIjpbIl9zcmMvbWVyZ2UudHMiXSwibmFtZXMiOltdLCJtYXBwaW5ncyI6Ijs7QUFBQSwyQ0FNcUI7QUFDckIsNkNBQXlDO0FBR3pDOzs7Ozs7Ozs7O0dBVUc7QUFDSCxTQUFnQixnQkFBZ0IsQ0FBQyxXQUFzQztJQUNyRSxJQUFJLFdBQVcsQ0FBQyxNQUFNLEtBQUssQ0FBQyxFQUFFO1FBQzVCLE9BQU8sRUFBQyxNQUFNLEVBQUUsRUFBRSxFQUFDLENBQUM7S0FDckI7SUFFRCxNQUFNLFlBQVksR0FBNkIsSUFBSSxHQUFHLEVBQUUsQ0FBQztJQUN6RCxLQUFLLE1BQU0sVUFBVSxJQUFJLFdBQVcsRUFBRTtRQUNwQyxLQUFLLE1BQU0sU0FBUyxJQUFJLFVBQVUsQ0FBQyxNQUFNLEVBQUU7WUFDekMsSUFBSSxVQUFVLEdBQTRCLFlBQVksQ0FBQyxHQUFHLENBQUMsU0FBUyxDQUFDLEdBQUcsQ0FBQyxDQUFDO1lBQzFFLElBQUksVUFBVSxLQUFLLFNBQVMsRUFBRTtnQkFDNUIsVUFBVSxHQUFHLEVBQUUsQ0FBQztnQkFDaEIsWUFBWSxDQUFDLEdBQUcsQ0FBQyxTQUFTLENBQUMsR0FBRyxFQUFFLFVBQVUsQ0FBQyxDQUFDO2FBQzdDO1lBQ0QsVUFBVSxDQUFDLElBQUksQ0FBQyxTQUFTLENBQUMsQ0FBQztTQUM1QjtLQUNGO0lBRUQsTUFBTSxNQUFNLEdBQWdCLEVBQUUsQ0FBQztJQUMvQixLQUFLLE1BQU0sT0FBTyxJQUFJLFlBQVksQ0FBQyxNQUFNLEVBQUUsRUFBRTtRQUMzQywrQkFBK0I7UUFDL0IsTUFBTSxDQUFDLElBQUksQ0FBQyxlQUFlLENBQUMsT0FBTyxDQUFFLENBQUMsQ0FBQztLQUN4QztJQUNELE1BQU0sTUFBTSxHQUFlLEVBQUMsTUFBTSxFQUFDLENBQUM7SUFFcEMsK0JBQW1CLENBQUMsTUFBTSxDQUFDLENBQUM7SUFDNUIsT0FBTyxNQUFNLENBQUM7QUFDaEIsQ0FBQztBQTFCRCw0Q0EwQkM7QUFFRDs7Ozs7Ozs7Ozs7R0FXRztBQUNILFNBQWdCLGVBQWUsQ0FBQyxVQUFvQztJQUNsRSxJQUFJLFVBQVUsQ0FBQyxNQUFNLEtBQUssQ0FBQyxFQUFFO1FBQzNCLE9BQU8sU0FBUyxDQUFDO0tBQ2xCO1NBQU0sSUFBSSxVQUFVLENBQUMsTUFBTSxLQUFLLENBQUMsRUFBRTtRQUNsQyxNQUFNLE1BQU0sR0FBYyxVQUFVLENBQUMsQ0FBQyxDQUFDLENBQUM7UUFDeEMsa0NBQXNCLENBQUMsTUFBTSxDQUFDLENBQUM7UUFDL0IsT0FBTyxNQUFNLENBQUM7S0FDZjtJQUVELE1BQU0sS0FBSyxHQUFjLFVBQVUsQ0FBQyxDQUFDLENBQUMsQ0FBQztJQUN2QyxNQUFNLFFBQVEsR0FBVyxLQUFLLENBQUMsUUFBUSxDQUFDO0lBQ3hDLE1BQU0sR0FBRyxHQUFXLEtBQUssQ0FBQyxHQUFHLENBQUM7SUFFOUIsTUFBTSxZQUFZLEdBQStCLElBQUksR0FBRyxFQUFFLENBQUM7SUFDM0QsS0FBSyxNQUFNLFNBQVMsSUFBSSxVQUFVLEVBQUU7UUFDbEMsS0FBSyxNQUFNLE9BQU8sSUFBSSxTQUFTLENBQUMsU0FBUyxFQUFFO1lBQ3pDLE1BQU0sU0FBUyxHQUFXLDBCQUEwQixDQUFDLE9BQU8sQ0FBQyxDQUFDO1lBQzlELElBQUksUUFBUSxHQUE4QixZQUFZLENBQUMsR0FBRyxDQUFDLFNBQVMsQ0FBQyxDQUFDO1lBRXRFLElBQUksUUFBUSxLQUFLLFNBQVM7Z0JBQ3hCLGlFQUFpRTtnQkFDakUsdURBQXVEO2dCQUN2RCxDQUFDLENBQUMsUUFBUSxDQUFDLENBQUMsQ0FBQyxDQUFDLGVBQWUsSUFBSSxPQUFPLENBQUMsZUFBZSxDQUFDLEVBQUU7Z0JBQzNELFFBQVEsR0FBRyxFQUFFLENBQUM7Z0JBQ2QsWUFBWSxDQUFDLEdBQUcsQ0FBQyxTQUFTLEVBQUUsUUFBUSxDQUFDLENBQUM7YUFDdkM7aUJBQU0sSUFBSSxRQUFRLENBQUMsQ0FBQyxDQUFDLENBQUMsZUFBZSxJQUFJLENBQUMsT0FBTyxDQUFDLGVBQWUsRUFBRTtnQkFDbEUscUVBQXFFO2dCQUNyRSx5Q0FBeUM7Z0JBQ3pDLFNBQVM7YUFDVjtZQUNELFFBQVEsQ0FBQyxJQUFJLENBQUMsT0FBTyxDQUFDLENBQUM7U0FDeEI7S0FDRjtJQUVELE1BQU0sU0FBUyxHQUFrQixFQUFFLENBQUM7SUFDcEMsS0FBSyxNQUFNLFFBQVEsSUFBSSxZQUFZLENBQUMsTUFBTSxFQUFFLEVBQUU7UUFDNUMsZ0NBQWdDO1FBQ2hDLFNBQVMsQ0FBQyxJQUFJLENBQUMsaUJBQWlCLENBQUMsUUFBUSxDQUFFLENBQUMsQ0FBQztLQUM5QztJQUVELE1BQU0sTUFBTSxHQUFjLEVBQUMsUUFBUSxFQUFFLEdBQUcsRUFBRSxTQUFTLEVBQUMsQ0FBQztJQUNyRCw4QkFBa0IsQ0FBQyxNQUFNLENBQUMsQ0FBQztJQUMzQixPQUFPLE1BQU0sQ0FBQztBQUNoQixDQUFDO0FBM0NELDBDQTJDQztBQUVEOzs7Ozs7Ozs7O0dBVUc7QUFDSCxTQUFTLDBCQUEwQixDQUFDLE9BQThCO0lBQ2hFLE1BQU0sU0FBUyxHQUFhLE9BQU8sQ0FBQyxNQUFNLENBQUMsQ0FBQyxDQUFDLENBQUM7SUFDOUMsT0FBTyxHQUFHLFNBQVMsQ0FBQyxXQUFXLENBQUMsUUFBUSxDQUFDLEVBQUUsQ0FBQyxJQUFJLFNBQVMsQ0FBQyxTQUFTLENBQUMsUUFBUSxDQUFDLEVBQUUsQ0FBQyxFQUFFLENBQUM7QUFDckYsQ0FBQztBQUVEOzs7Ozs7Ozs7OztHQVdHO0FBQ0gsU0FBZ0IsaUJBQWlCLENBQUMsUUFBb0M7SUFDcEUsSUFBSSxRQUFRLENBQUMsTUFBTSxLQUFLLENBQUMsRUFBRTtRQUN6QixPQUFPLFNBQVMsQ0FBQztLQUNsQjtTQUFNLElBQUksUUFBUSxDQUFDLE1BQU0sS0FBSyxDQUFDLEVBQUU7UUFDaEMsTUFBTSxNQUFNLEdBQWdCLFFBQVEsQ0FBQyxDQUFDLENBQUMsQ0FBQztRQUN4QyxnQ0FBb0IsQ0FBQyxNQUFNLENBQUMsQ0FBQztRQUM3QixPQUFPLE1BQU0sQ0FBQztLQUNmO0lBRUQsTUFBTSxZQUFZLEdBQVcsUUFBUSxDQUFDLENBQUMsQ0FBQyxDQUFDLFlBQVksQ0FBQztJQUV0RCxNQUFNLEtBQUssR0FBZ0IsRUFBRSxDQUFDO0lBQzlCLEtBQUssTUFBTSxPQUFPLElBQUksUUFBUSxFQUFFO1FBQzlCLGlDQUFpQztRQUNqQyxnQ0FBZ0M7UUFDaEMsS0FBSyxDQUFDLElBQUksQ0FBQyxzQkFBUyxDQUFDLGdCQUFnQixDQUFDLE9BQU8sQ0FBQyxNQUFNLENBQUUsQ0FBQyxDQUFDO0tBQ3pEO0lBRUQsNkJBQTZCO0lBQzdCLE1BQU0sVUFBVSxHQUFjLGVBQWUsQ0FBQyxLQUFLLENBQUUsQ0FBQztJQUN0RCw4QkFBa0IsQ0FBQyxVQUFVLENBQUMsQ0FBQztJQUMvQixNQUFNLE1BQU0sR0FBZSxVQUFVLENBQUMsUUFBUSxFQUFFLENBQUM7
|