tor-browser

tree.ts (23511B)

---

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]);
 }
}