Source code
Revision control
Copy as Markdown
Other Tools
import { loadMetadataForSuite, TestMetadataListing } from '../framework/metadata.js';
import { globalTestConfig } from '../framework/test_config.js';
import { RunCase, RunFn } from '../internal/test_group.js';
import { assert, now } from '../util/util.js';
import { TestFileLoader } from './file_loader.js';
import { TestParamsRW } from './params_utils.js';
import { comparePublicParamsPaths, compareQueries, Ordering } from './query/compare.js';
import {
TestQuery,
TestQueryMultiCase,
TestQuerySingleCase,
TestQueryMultiFile,
TestQueryMultiTest,
} from './query/query.js';
import { kBigSeparator, kWildcard, kPathSeparator, kParamSeparator } from './query/separators.js';
import { stringifySingleParam } from './query/stringify_params.js';
import { StacklessError } from './util.js';
// `loadTreeForQuery()` loads a TestTree for a given queryToLoad.
// The resulting tree is a linked-list all the way from `suite:*` to queryToLoad,
// and under queryToLoad is a tree containing every case matched by queryToLoad.
//
// `subqueriesToExpand` influences the `collapsible` flag on nodes in the resulting tree.
// A node is considered "collapsible" if none of the subqueriesToExpand is a StrictSubset
// of that node.
//
// In WebKit/Blink-style web_tests, an expectation file marks individual cts.https.html "variants
// as "Failure", "Crash", etc. By passing in the list of expectations as the subqueriesToExpand,
// we can programmatically subdivide the cts.https.html "variants" list to be able to implement
// arbitrarily-fine suppressions (instead of having to suppress entire test files, which would
// lose a lot of coverage).
//
// `iterateCollapsedNodes()` produces the list of queries for the variants list.
//
// Though somewhat complicated, this system has important benefits:
// - Avoids having to suppress entire test files, which would cause large test coverage loss.
// - Minimizes the number of page loads needed for fine-grained suppressions.
// (In the naive case, we could do one page load per test case - but the test suite would
// take impossibly long to run.)
// - Enables developers to put any number of tests in one file as appropriate, without worrying
// about expectation granularity.
interface TestTreeNodeBase<T extends TestQuery> {
readonly query: T;
/**
* Readable "relative" name for display in standalone runner.
* Not always the exact relative name, because sometimes there isn't
* one (e.g. s:f:* relative to s:f,*), but something that is readable.
*/
readonly readableRelativeName: string;
subtreeCounts?: { tests: number; nodesWithTODO: number; totalTimeMS: number };
subcaseCount?: number;
}
export interface TestSubtree<T extends TestQuery = TestQuery> extends TestTreeNodeBase<T> {
readonly children: Map<string, TestTreeNode>;
collapsible: boolean;
description?: string;
readonly testCreationStack?: Error;
}
export interface TestTreeLeaf extends TestTreeNodeBase<TestQuerySingleCase> {
readonly run: RunFn;
readonly isUnimplemented?: boolean;
subtreeCounts?: undefined;
subcaseCount: number;
}
export type TestTreeNode = TestSubtree | TestTreeLeaf;
/**
* When iterating through "collapsed" tree nodes, indicates how many "query levels" to traverse
* through before starting to collapse nodes.
*
* Corresponds with TestQueryLevel, but excludes 4 (SingleCase):
* - 1 = MultiFile. Expands so every file is in the collapsed tree.
* - 2 = MultiTest. Expands so every test is in the collapsed tree.
* - 3 = MultiCase. Expands so every case is in the collapsed tree (i.e. collapsing disabled).
*/
export type ExpandThroughLevel = 1 | 2 | 3;
export class TestTree {
/**
* The `queryToLoad` that this test tree was created for.
* Test trees are always rooted at `suite:*`, but they only contain nodes that fit
* within `forQuery`.
*
* This is used for `iterateCollapsedNodes` which only starts collapsing at the next
* `TestQueryLevel` after `forQuery`.
*/
readonly forQuery: TestQuery;
readonly root: TestSubtree;
private constructor(forQuery: TestQuery, root: TestSubtree) {
this.forQuery = forQuery;
this.root = root;
assert(
root.query.level === 1 && root.query.depthInLevel === 0,
'TestTree root must be the root (suite:*)'
);
}
static async create(
forQuery: TestQuery,
root: TestSubtree,
maxChunkTime: number
): Promise<TestTree> {
const suite = forQuery.suite;
let chunking = undefined;
if (Number.isFinite(maxChunkTime)) {
const metadata = loadMetadataForSuite(`./src/${suite}`);
assert(metadata !== null, `metadata for ${suite} is missing, but maxChunkTime was requested`);
chunking = { metadata, maxChunkTime };
}
await TestTree.propagateCounts(root, chunking);
return new TestTree(forQuery, root);
}
/**
* Iterate through the leaves of a version of the tree which has been pruned to exclude
* subtrees which:
* - are at a deeper `TestQueryLevel` than `this.forQuery`, and
* - were not a `Ordering.StrictSubset` of any of the `subqueriesToExpand` during tree creation.
*/
iterateCollapsedNodes({
includeIntermediateNodes = false,
includeEmptySubtrees = false,
alwaysExpandThroughLevel,
}: {
/** Whether to include intermediate tree nodes or only collapsed-leaves. */
includeIntermediateNodes?: boolean;
/** Whether to include collapsed-leaves with no children. */
includeEmptySubtrees?: boolean;
/** Never collapse nodes up through this level. */
alwaysExpandThroughLevel: ExpandThroughLevel;
}): IterableIterator<Readonly<TestTreeNode>> {
const expandThroughLevel = Math.max(this.forQuery.level, alwaysExpandThroughLevel);
return TestTree.iterateSubtreeNodes(this.root, {
includeIntermediateNodes,
includeEmptySubtrees,
expandThroughLevel,
});
}
iterateLeaves(): IterableIterator<Readonly<TestTreeLeaf>> {
return TestTree.iterateSubtreeLeaves(this.root);
}
/**
* Dissolve nodes which have only one child, e.g.:
* a,* { a,b,* { a,b:* { ... } } }
* collapses down into:
* a,* { a,b:* { ... } }
* which is less needlessly verbose when displaying the tree in the standalone runner.
*/
dissolveSingleChildTrees(): void {
const newRoot = dissolveSingleChildTrees(this.root);
assert(newRoot === this.root);
}
toString(): string {
return TestTree.subtreeToString('(root)', this.root, '');
}
static *iterateSubtreeNodes(
subtree: TestSubtree,
opts: {
includeIntermediateNodes: boolean;
includeEmptySubtrees: boolean;
expandThroughLevel: number;
}
): IterableIterator<TestTreeNode> {
if (opts.includeIntermediateNodes) {
yield subtree;
}
for (const [, child] of subtree.children) {
if ('children' in child) {
// Is a subtree
const collapsible = child.collapsible && child.query.level > opts.expandThroughLevel;
if (child.children.size > 0 && !collapsible) {
yield* TestTree.iterateSubtreeNodes(child, opts);
} else if (child.children.size > 0 || opts.includeEmptySubtrees) {
// Don't yield empty subtrees (e.g. files with no tests) unless includeEmptySubtrees
yield child;
}
} else {
// Is a leaf
yield child;
}
}
}
static *iterateSubtreeLeaves(subtree: TestSubtree): IterableIterator<TestTreeLeaf> {
for (const [, child] of subtree.children) {
if ('children' in child) {
yield* TestTree.iterateSubtreeLeaves(child);
} else {
yield child;
}
}
}
/** Propagate the subtreeTODOs/subtreeTests state upward from leaves to parent nodes. */
static async propagateCounts(
subtree: TestSubtree,
chunking: { metadata: TestMetadataListing; maxChunkTime: number } | undefined
): Promise<{ tests: number; nodesWithTODO: number; totalTimeMS: number; subcaseCount: number }> {
subtree.subtreeCounts ??= { tests: 0, nodesWithTODO: 0, totalTimeMS: 0 };
subtree.subcaseCount = 0;
for (const [, child] of subtree.children) {
if ('children' in child) {
const counts = await TestTree.propagateCounts(child, chunking);
subtree.subtreeCounts.tests += counts.tests;
subtree.subtreeCounts.nodesWithTODO += counts.nodesWithTODO;
subtree.subtreeCounts.totalTimeMS += counts.totalTimeMS;
subtree.subcaseCount += counts.subcaseCount;
} else {
subtree.subcaseCount = child.subcaseCount;
}
}
// If we're chunking based on a maxChunkTime, then at each
// TestQueryMultiCase node of the tree we look at its total time. If the
// total time is larger than the maxChunkTime, we set collapsible=false to
// make sure it gets split up in the output. Note:
// - TestQueryMultiTest and higher nodes are never set to collapsible anyway, so we ignore them.
// - TestQuerySingleCase nodes can't be collapsed, so we ignore them.
if (chunking && subtree.query instanceof TestQueryMultiCase) {
const testLevelQuery = new TestQueryMultiCase(
subtree.query.suite,
subtree.query.filePathParts,
subtree.query.testPathParts,
{}
).toString();
const metadata = chunking.metadata;
const subcaseTiming: number | undefined = metadata[testLevelQuery]?.subcaseMS;
if (subcaseTiming !== undefined) {
const totalTiming = subcaseTiming * subtree.subcaseCount;
subtree.subtreeCounts.totalTimeMS = totalTiming;
if (totalTiming > chunking.maxChunkTime) {
subtree.collapsible = false;
}
}
}
return { ...subtree.subtreeCounts, subcaseCount: subtree.subcaseCount ?? 0 };
}
/** Displays counts in the format `(Nodes with TODOs) / (Total test count)`. */
static countsToString(tree: TestTreeNode): string {
if (tree.subtreeCounts) {
return `${tree.subtreeCounts.nodesWithTODO} / ${tree.subtreeCounts.tests}`;
} else {
return '';
}
}
static subtreeToString(name: string, tree: TestTreeNode, indent: string): string {
const collapsible = 'run' in tree ? '>' : tree.collapsible ? '+' : '-';
let s =
indent +
`${collapsible} ${TestTree.countsToString(tree)} ${JSON.stringify(name)} => ${tree.query}`;
if ('children' in tree) {
if (tree.description !== undefined) {
s += `\n${indent} | ${JSON.stringify(tree.description)}`;
}
for (const [name, child] of tree.children) {
s += '\n' + TestTree.subtreeToString(name, child, indent + ' ');
}
}
return s;
}
}
// MAINTENANCE_TODO: Consider having subqueriesToExpand actually impact the depth-order of params
// in the tree.
export async function loadTreeForQuery(
loader: TestFileLoader,
queryToLoad: TestQuery,
{
subqueriesToExpand,
fullyExpandSubtrees = [],
maxChunkTime = Infinity,
}: { subqueriesToExpand: TestQuery[]; fullyExpandSubtrees?: TestQuery[]; maxChunkTime?: number }
): Promise<TestTree> {
const suite = queryToLoad.suite;
const specs = await loader.listing(suite);
const subqueriesToExpandEntries = Array.from(subqueriesToExpand.entries());
const seenSubqueriesToExpand: boolean[] = new Array(subqueriesToExpand.length);
seenSubqueriesToExpand.fill(false);
const isCollapsible = (subquery: TestQuery) =>
subqueriesToExpandEntries.every(([i, toExpand]) => {
const ordering = compareQueries(toExpand, subquery);
// If toExpand == subquery, no expansion is needed (but it's still "seen").
if (ordering === Ordering.Equal) seenSubqueriesToExpand[i] = true;
return ordering !== Ordering.StrictSubset;
}) &&
fullyExpandSubtrees.every(toExpand => {
const ordering = compareQueries(toExpand, subquery);
return ordering === Ordering.Unordered;
});
// L0 = suite-level, e.g. suite:*
// L1 = file-level, e.g. suite:a,b:*
// L2 = test-level, e.g. suite:a,b:c,d:*
// L3 = case-level, e.g. suite:a,b:c,d:
let foundCase = false;
// L0 is suite:*
const subtreeL0 = makeTreeForSuite(suite, isCollapsible);
const imports_start = now();
const pEntriesWithImports = []; // Promise<entry with importedSpec>[]
for (const entry of specs) {
if (entry.file.length === 0 && 'readme' in entry) {
// Suite-level readme.
setSubtreeDescriptionAndCountTODOs(subtreeL0, entry.readme);
continue;
}
{
const queryL1 = new TestQueryMultiFile(suite, entry.file);
const orderingL1 = compareQueries(queryL1, queryToLoad);
if (orderingL1 === Ordering.Unordered) {
// File path is not matched by this query.
continue;
}
}
// We're going to be fetching+importing a bunch of things, so do it in async.
const pEntryWithImport = (async () => {
if ('readme' in entry) {
return entry;
} else {
return {
...entry,
importedSpec: await loader.importSpecFile(queryToLoad.suite, entry.file),
};
}
})();
const kForceSerialImporting = false;
if (kForceSerialImporting) {
await pEntryWithImport;
}
pEntriesWithImports.push(pEntryWithImport);
}
const entriesWithImports = await Promise.all(pEntriesWithImports);
if (globalTestConfig.frameworkDebugLog) {
const imported_time = performance.now() - imports_start;
globalTestConfig.frameworkDebugLog(
`Imported importedSpecFiles[${entriesWithImports.length}] in ${imported_time}ms.`
);
}
for (const entry of entriesWithImports) {
if ('readme' in entry) {
// Entry is a README that is an ancestor or descendant of the query.
// (It's included for display in the standalone runner.)
// readmeSubtree is suite:a,b,*
// (This is always going to dedup with a file path, if there are any test spec files under
// the directory that has the README).
const readmeSubtree: TestSubtree<TestQueryMultiFile> = addSubtreeForDirPath(
subtreeL0,
entry.file,
isCollapsible
);
setSubtreeDescriptionAndCountTODOs(readmeSubtree, entry.readme);
continue;
}
// Entry is a spec file.
const spec = entry.importedSpec;
// subtreeL1 is suite:a,b:*
const subtreeL1: TestSubtree<TestQueryMultiTest> = addSubtreeForFilePath(
subtreeL0,
entry.file,
isCollapsible
);
setSubtreeDescriptionAndCountTODOs(subtreeL1, spec.description);
let groupHasTests = false;
for (const t of spec.g.iterate()) {
groupHasTests = true;
{
const queryL2 = new TestQueryMultiCase(suite, entry.file, t.testPath, {});
const orderingL2 = compareQueries(queryL2, queryToLoad);
if (orderingL2 === Ordering.Unordered) {
// Test path is not matched by this query.
continue;
}
}
// subtreeL2 is suite:a,b:c,d:*
const subtreeL2: TestSubtree<TestQueryMultiCase> = addSubtreeForTestPath(
subtreeL1,
t.testPath,
t.testCreationStack,
isCollapsible
);
// This is 1 test. Set tests=1 then count TODOs.
subtreeL2.subtreeCounts ??= { tests: 1, nodesWithTODO: 0, totalTimeMS: 0 };
if (t.description) setSubtreeDescriptionAndCountTODOs(subtreeL2, t.description);
let caseFilter = null;
if ('params' in queryToLoad) {
caseFilter = queryToLoad.params;
}
// MAINTENANCE_TODO: If tree generation gets too slow, avoid actually iterating the cases in a
// file if there's no need to (based on the subqueriesToExpand).
for (const c of t.iterate(caseFilter)) {
// iterate() guarantees c's query is equal to or a subset of queryToLoad.
if (queryToLoad instanceof TestQuerySingleCase) {
// A subset is OK if it's TestQueryMultiCase, but for SingleCase it must match exactly.
const ordering = comparePublicParamsPaths(c.id.params, queryToLoad.params);
if (ordering !== Ordering.Equal) {
continue;
}
}
// Leaf for case is suite:a,b:c,d:x=1;y=2
addLeafForCase(subtreeL2, c, isCollapsible);
foundCase = true;
}
}
if (!groupHasTests && !subtreeL1.subtreeCounts) {
throw new StacklessError(
`${subtreeL1.query} has no tests - it must have "TODO" in its description`
);
}
}
for (const [i, sq] of subqueriesToExpandEntries) {
const subquerySeen = seenSubqueriesToExpand[i];
if (!subquerySeen) {
throw new StacklessError(
`subqueriesToExpand entry did not match anything \
(could be wrong, or could be redundant with a previous subquery):\n ${sq.toString()}`
);
}
}
assert(foundCase, `Query \`${queryToLoad.toString()}\` does not match any cases`);
return TestTree.create(queryToLoad, subtreeL0, maxChunkTime);
}
function setSubtreeDescriptionAndCountTODOs(
subtree: TestSubtree<TestQueryMultiFile>,
description: string
) {
assert(subtree.description === undefined);
subtree.description = description.trim();
subtree.subtreeCounts ??= { tests: 0, nodesWithTODO: 0, totalTimeMS: 0 };
if (subtree.description.indexOf('TODO') !== -1) {
subtree.subtreeCounts.nodesWithTODO++;
}
}
function makeTreeForSuite(
suite: string,
isCollapsible: (sq: TestQuery) => boolean
): TestSubtree<TestQueryMultiFile> {
const query = new TestQueryMultiFile(suite, []);
return {
readableRelativeName: suite + kBigSeparator,
query,
children: new Map(),
collapsible: isCollapsible(query),
};
}
function addSubtreeForDirPath(
tree: TestSubtree<TestQueryMultiFile>,
file: string[],
isCollapsible: (sq: TestQuery) => boolean
): TestSubtree<TestQueryMultiFile> {
const subqueryFile: string[] = [];
// To start, tree is suite:*
// This loop goes from that -> suite:a,* -> suite:a,b,*
for (const part of file) {
subqueryFile.push(part);
tree = getOrInsertSubtree(part, tree, () => {
const query = new TestQueryMultiFile(tree.query.suite, subqueryFile);
return {
readableRelativeName: part + kPathSeparator + kWildcard,
query,
collapsible: isCollapsible(query),
};
});
}
return tree;
}
function addSubtreeForFilePath(
tree: TestSubtree<TestQueryMultiFile>,
file: string[],
isCollapsible: (sq: TestQuery) => boolean
): TestSubtree<TestQueryMultiTest> {
// To start, tree is suite:*
// This goes from that -> suite:a,* -> suite:a,b,*
tree = addSubtreeForDirPath(tree, file, isCollapsible);
// This goes from that -> suite:a,b:*
const subtree = getOrInsertSubtree('', tree, () => {
const query = new TestQueryMultiTest(tree.query.suite, tree.query.filePathParts, []);
assert(file.length > 0, 'file path is empty');
return {
readableRelativeName: file[file.length - 1] + kBigSeparator + kWildcard,
query,
collapsible: isCollapsible(query),
};
});
return subtree;
}
function addSubtreeForTestPath(
tree: TestSubtree<TestQueryMultiTest>,
test: readonly string[],
testCreationStack: Error,
isCollapsible: (sq: TestQuery) => boolean
): TestSubtree<TestQueryMultiCase> {
const subqueryTest: string[] = [];
// To start, tree is suite:a,b:*
// This loop goes from that -> suite:a,b:c,* -> suite:a,b:c,d,*
for (const part of test) {
subqueryTest.push(part);
tree = getOrInsertSubtree(part, tree, () => {
const query = new TestQueryMultiTest(
tree.query.suite,
tree.query.filePathParts,
subqueryTest
);
return {
readableRelativeName: part + kPathSeparator + kWildcard,
query,
collapsible: isCollapsible(query),
};
});
}
// This goes from that -> suite:a,b:c,d:*
return getOrInsertSubtree('', tree, () => {
const query = new TestQueryMultiCase(
tree.query.suite,
tree.query.filePathParts,
subqueryTest,
{}
);
assert(subqueryTest.length > 0, 'subqueryTest is empty');
return {
readableRelativeName: subqueryTest[subqueryTest.length - 1] + kBigSeparator + kWildcard,
kWildcard,
query,
testCreationStack,
collapsible: isCollapsible(query),
};
});
}
function addLeafForCase(
tree: TestSubtree<TestQueryMultiTest>,
t: RunCase,
checkCollapsible: (sq: TestQuery) => boolean
): void {
const query = tree.query;
let name: string = '';
const subqueryParams: TestParamsRW = {};
// To start, tree is suite:a,b:c,d:*
// This loop goes from that -> suite:a,b:c,d:x=1;* -> suite:a,b:c,d:x=1;y=2;*
for (const [k, v] of Object.entries(t.id.params)) {
name = stringifySingleParam(k, v);
subqueryParams[k] = v;
tree = getOrInsertSubtree(name, tree, () => {
const subquery = new TestQueryMultiCase(
query.suite,
query.filePathParts,
query.testPathParts,
subqueryParams
);
return {
readableRelativeName: name + kParamSeparator + kWildcard,
query: subquery,
collapsible: checkCollapsible(subquery),
};
});
}
// This goes from that -> suite:a,b:c,d:x=1;y=2
const subquery = new TestQuerySingleCase(
query.suite,
query.filePathParts,
query.testPathParts,
subqueryParams
);
checkCollapsible(subquery); // mark seenSubqueriesToExpand
insertLeaf(tree, subquery, t);
}
function getOrInsertSubtree<T extends TestQuery>(
key: string,
parent: TestSubtree,
createSubtree: () => Omit<TestSubtree<T>, 'children'>
): TestSubtree<T> {
let v: TestSubtree<T>;
const child = parent.children.get(key);
if (child !== undefined) {
assert('children' in child); // Make sure cached subtree is not actually a leaf
v = child as TestSubtree<T>;
} else {
v = { ...createSubtree(), children: new Map() };
parent.children.set(key, v);
}
return v;
}
function insertLeaf(parent: TestSubtree, query: TestQuerySingleCase, t: RunCase) {
const leaf: TestTreeLeaf = {
readableRelativeName: readableNameForCase(query),
query,
run: (rec, expectations) => t.run(rec, query, expectations || []),
isUnimplemented: t.isUnimplemented,
subcaseCount: t.computeSubcaseCount(),
};
// This is a leaf (e.g. s:f:t:x=1;* -> s:f:t:x=1). The key is always ''.
const key = '';
assert(!parent.children.has(key), `Duplicate testcase: ${query}`);
parent.children.set(key, leaf);
}
function dissolveSingleChildTrees(tree: TestTreeNode): TestTreeNode {
if ('children' in tree) {
const shouldDissolveThisTree =
tree.children.size === 1 && tree.query.depthInLevel !== 0 && tree.description === undefined;
if (shouldDissolveThisTree) {
// Loops exactly once
for (const [, child] of tree.children) {
// Recurse on child
return dissolveSingleChildTrees(child);
}
}
for (const [k, child] of tree.children) {
// Recurse on each child
const newChild = dissolveSingleChildTrees(child);
if (newChild !== child) {
tree.children.set(k, newChild);
}
}
}
return tree;
}
/** Generate a readable relative name for a case (used in standalone). */
function readableNameForCase(query: TestQuerySingleCase): string {
const paramsKeys = Object.keys(query.params);
if (paramsKeys.length === 0) {
return query.testPathParts[query.testPathParts.length - 1] + kBigSeparator;
} else {
const lastKey = paramsKeys[paramsKeys.length - 1];
return stringifySingleParam(lastKey, query.params[lastKey]);
}
}