From 36d22d82aa202bb199967e9512281e9a53db42c9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 21:33:14 +0200 Subject: Adding upstream version 115.7.0esr. Signed-off-by: Daniel Baumann --- .../checkout/src/common/internal/file_loader.ts | 95 +++ .../src/common/internal/logging/log_message.ts | 44 ++ .../checkout/src/common/internal/logging/logger.ts | 30 + .../checkout/src/common/internal/logging/result.ts | 21 + .../common/internal/logging/test_case_recorder.ts | 158 +++++ .../checkout/src/common/internal/params_utils.ts | 124 ++++ .../checkout/src/common/internal/query/compare.ts | 94 +++ .../common/internal/query/encode_selectively.ts | 23 + .../src/common/internal/query/json_param_value.ts | 83 +++ .../src/common/internal/query/parseQuery.ts | 155 +++++ .../checkout/src/common/internal/query/query.ts | 262 +++++++++ .../src/common/internal/query/separators.ts | 14 + .../src/common/internal/query/stringify_params.ts | 44 ++ .../src/common/internal/query/validQueryPart.ts | 2 + .../cts/checkout/src/common/internal/stack.ts | 82 +++ .../cts/checkout/src/common/internal/test_group.ts | 646 +++++++++++++++++++++ .../src/common/internal/test_suite_listing.ts | 15 + .../tests/cts/checkout/src/common/internal/tree.ts | 575 ++++++++++++++++++ .../tests/cts/checkout/src/common/internal/util.ts | 10 + .../cts/checkout/src/common/internal/version.ts | 1 + 20 files changed, 2478 insertions(+) create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/file_loader.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/logging/log_message.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/logging/logger.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/logging/result.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/logging/test_case_recorder.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/params_utils.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/query/compare.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/query/encode_selectively.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/query/json_param_value.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/query/parseQuery.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/query/query.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/query/separators.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/query/stringify_params.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/query/validQueryPart.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/stack.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/test_group.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/test_suite_listing.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/tree.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/util.ts create mode 100644 dom/webgpu/tests/cts/checkout/src/common/internal/version.ts (limited to 'dom/webgpu/tests/cts/checkout/src/common/internal') diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/file_loader.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/file_loader.ts new file mode 100644 index 0000000000..922d6a09dd --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/file_loader.ts @@ -0,0 +1,95 @@ +import { IterableTestGroup } from '../internal/test_group.js'; +import { assert } from '../util/util.js'; + +import { parseQuery } from './query/parseQuery.js'; +import { TestQuery } from './query/query.js'; +import { TestSuiteListing } from './test_suite_listing.js'; +import { loadTreeForQuery, TestTree, TestTreeLeaf } from './tree.js'; + +// A listing file, e.g. either of: +// - `src/webgpu/listing.ts` (which is dynamically computed, has a Promise) +// - `out/webgpu/listing.js` (which is pre-baked, has a TestSuiteListing) +interface ListingFile { + listing: Promise | TestSuiteListing; +} + +// A .spec.ts file, as imported. +export interface SpecFile { + readonly description: string; + readonly g: IterableTestGroup; +} + +export interface ImportInfo { + url: string; +} + +interface TestFileLoaderEventMap { + import: MessageEvent; + finish: MessageEvent; +} + +export interface TestFileLoader extends EventTarget { + addEventListener( + type: K, + listener: (this: TestFileLoader, ev: TestFileLoaderEventMap[K]) => void, + options?: boolean | AddEventListenerOptions + ): void; + addEventListener( + type: string, + listener: EventListenerOrEventListenerObject, + options?: boolean | AddEventListenerOptions + ): void; + removeEventListener( + type: K, + listener: (this: TestFileLoader, ev: TestFileLoaderEventMap[K]) => void, + options?: boolean | EventListenerOptions + ): void; + removeEventListener( + type: string, + listener: EventListenerOrEventListenerObject, + options?: boolean | EventListenerOptions + ): void; +} + +// Base class for DefaultTestFileLoader and FakeTestFileLoader. +export abstract class TestFileLoader extends EventTarget { + abstract listing(suite: string): Promise; + protected abstract import(path: string): Promise; + + importSpecFile(suite: string, path: string[]): Promise { + const url = `${suite}/${path.join('/')}.spec.js`; + this.dispatchEvent( + new MessageEvent('import', { data: { url } }) + ); + return this.import(url); + } + + async loadTree(query: TestQuery, subqueriesToExpand: string[] = []): Promise { + const tree = await loadTreeForQuery( + this, + query, + subqueriesToExpand.map(s => { + const q = parseQuery(s); + assert(q.level >= 2, () => `subqueriesToExpand entries should not be multi-file:\n ${q}`); + return q; + }) + ); + this.dispatchEvent(new MessageEvent('finish')); + return tree; + } + + async loadCases(query: TestQuery): Promise> { + const tree = await this.loadTree(query); + return tree.iterateLeaves(); + } +} + +export class DefaultTestFileLoader extends TestFileLoader { + async listing(suite: string): Promise { + return ((await import(`../../${suite}/listing.js`)) as ListingFile).listing; + } + + import(path: string): Promise { + return import(`../../${path}`); + } +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/logging/log_message.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/logging/log_message.ts new file mode 100644 index 0000000000..ee006cdeb3 --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/logging/log_message.ts @@ -0,0 +1,44 @@ +import { ErrorWithExtra } from '../../util/util.js'; +import { extractImportantStackTrace } from '../stack.js'; + +export class LogMessageWithStack extends Error { + readonly extra: unknown; + + private stackHiddenMessage: string | undefined = undefined; + + constructor(name: string, ex: Error | ErrorWithExtra) { + super(ex.message); + + this.name = name; + this.stack = ex.stack; + if ('extra' in ex) { + this.extra = ex.extra; + } + } + + /** Set a flag so the stack is not printed in toJSON(). */ + setStackHidden(stackHiddenMessage: string) { + this.stackHiddenMessage ??= stackHiddenMessage; + } + + toJSON(): string { + let m = this.name; + if (this.message) m += ': ' + this.message; + if (this.stack) { + if (this.stackHiddenMessage === undefined) { + m += '\n' + extractImportantStackTrace(this); + } else if (this.stackHiddenMessage) { + m += `\n at (elided: ${this.stackHiddenMessage})`; + } + } + return m; + } +} + +/** + * Returns a string, nicely indented, for debug logs. + * This is used in the cmdline and wpt runtimes. In WPT, it shows up in the `*-actual.txt` file. + */ +export function prettyPrintLog(log: LogMessageWithStack): string { + return ' - ' + log.toJSON().replace(/\n/g, '\n '); +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/logging/logger.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/logging/logger.ts new file mode 100644 index 0000000000..e4526cff54 --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/logging/logger.ts @@ -0,0 +1,30 @@ +import { version } from '../version.js'; + +import { LiveTestCaseResult } from './result.js'; +import { TestCaseRecorder } from './test_case_recorder.js'; + +export type LogResults = Map; + +export class Logger { + static globalDebugMode: boolean = false; + + readonly overriddenDebugMode: boolean | undefined; + readonly results: LogResults = new Map(); + + constructor({ overrideDebugMode }: { overrideDebugMode?: boolean } = {}) { + this.overriddenDebugMode = overrideDebugMode; + } + + record(name: string): [TestCaseRecorder, LiveTestCaseResult] { + const result: LiveTestCaseResult = { status: 'running', timems: -1 }; + this.results.set(name, result); + return [ + new TestCaseRecorder(result, this.overriddenDebugMode ?? Logger.globalDebugMode), + result, + ]; + } + + asJSON(space?: number): string { + return JSON.stringify({ version, results: Array.from(this.results) }, undefined, space); + } +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/logging/result.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/logging/result.ts new file mode 100644 index 0000000000..0de661b50c --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/logging/result.ts @@ -0,0 +1,21 @@ +import { LogMessageWithStack } from './log_message.js'; + +// MAINTENANCE_TODO: Add warn expectations +export type Expectation = 'pass' | 'skip' | 'fail'; + +export type Status = 'running' | 'warn' | Expectation; + +export interface TestCaseResult { + status: Status; + timems: number; +} + +export interface LiveTestCaseResult extends TestCaseResult { + logs?: LogMessageWithStack[]; +} + +export interface TransferredTestCaseResult extends TestCaseResult { + // When transferred from a worker, a LogMessageWithStack turns into a generic Error + // (its prototype gets lost and replaced with Error). + logs?: Error[]; +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/logging/test_case_recorder.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/logging/test_case_recorder.ts new file mode 100644 index 0000000000..7507bbdec6 --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/logging/test_case_recorder.ts @@ -0,0 +1,158 @@ +import { SkipTestCase, UnexpectedPassError } from '../../framework/fixture.js'; +import { globalTestConfig } from '../../framework/test_config.js'; +import { now, assert } from '../../util/util.js'; + +import { LogMessageWithStack } from './log_message.js'; +import { Expectation, LiveTestCaseResult } from './result.js'; + +enum LogSeverity { + Pass = 0, + Skip = 1, + Warn = 2, + ExpectFailed = 3, + ValidationFailed = 4, + ThrewException = 5, +} + +const kMaxLogStacks = 2; +const kMinSeverityForStack = LogSeverity.Warn; + +/** Holds onto a LiveTestCaseResult owned by the Logger, and writes the results into it. */ +export class TestCaseRecorder { + private result: LiveTestCaseResult; + private inSubCase: boolean = false; + private subCaseStatus = LogSeverity.Pass; + private finalCaseStatus = LogSeverity.Pass; + private hideStacksBelowSeverity = kMinSeverityForStack; + private startTime = -1; + private logs: LogMessageWithStack[] = []; + private logLinesAtCurrentSeverity = 0; + private debugging = false; + /** Used to dedup log messages which have identical stacks. */ + private messagesForPreviouslySeenStacks = new Map(); + + constructor(result: LiveTestCaseResult, debugging: boolean) { + this.result = result; + this.debugging = debugging; + } + + start(): void { + assert(this.startTime < 0, 'TestCaseRecorder cannot be reused'); + this.startTime = now(); + } + + finish(): void { + assert(this.startTime >= 0, 'finish() before start()'); + + const timeMilliseconds = now() - this.startTime; + // Round to next microsecond to avoid storing useless .xxxx00000000000002 in results. + this.result.timems = Math.ceil(timeMilliseconds * 1000) / 1000; + + // Convert numeric enum back to string (but expose 'exception' as 'fail') + this.result.status = + this.finalCaseStatus === LogSeverity.Pass + ? 'pass' + : this.finalCaseStatus === LogSeverity.Skip + ? 'skip' + : this.finalCaseStatus === LogSeverity.Warn + ? 'warn' + : 'fail'; // Everything else is an error + + this.result.logs = this.logs; + } + + beginSubCase() { + this.subCaseStatus = LogSeverity.Pass; + this.inSubCase = true; + } + + endSubCase(expectedStatus: Expectation) { + try { + if (expectedStatus === 'fail') { + if (this.subCaseStatus <= LogSeverity.Warn) { + throw new UnexpectedPassError(); + } else { + this.subCaseStatus = LogSeverity.Pass; + } + } + } finally { + this.inSubCase = false; + if (this.subCaseStatus > this.finalCaseStatus) { + this.finalCaseStatus = this.subCaseStatus; + } + } + } + + injectResult(injectedResult: LiveTestCaseResult): void { + Object.assign(this.result, injectedResult); + } + + debug(ex: Error): void { + if (!this.debugging) return; + this.logImpl(LogSeverity.Pass, 'DEBUG', ex); + } + + info(ex: Error): void { + this.logImpl(LogSeverity.Pass, 'INFO', ex); + } + + skipped(ex: SkipTestCase): void { + this.logImpl(LogSeverity.Skip, 'SKIP', ex); + } + + warn(ex: Error): void { + this.logImpl(LogSeverity.Warn, 'WARN', ex); + } + + expectationFailed(ex: Error): void { + this.logImpl(LogSeverity.ExpectFailed, 'EXPECTATION FAILED', ex); + } + + validationFailed(ex: Error): void { + this.logImpl(LogSeverity.ValidationFailed, 'VALIDATION FAILED', ex); + } + + threw(ex: unknown): void { + if (ex instanceof SkipTestCase) { + this.skipped(ex); + return; + } + this.logImpl(LogSeverity.ThrewException, 'EXCEPTION', ex); + } + + private logImpl(level: LogSeverity, name: string, baseException: unknown): void { + assert(baseException instanceof Error, 'test threw a non-Error object'); + globalTestConfig.testHeartbeatCallback(); + const logMessage = new LogMessageWithStack(name, baseException); + + // Final case status should be the "worst" of all log entries. + if (this.inSubCase) { + if (level > this.subCaseStatus) this.subCaseStatus = level; + } else { + if (level > this.finalCaseStatus) this.finalCaseStatus = level; + } + + // setFirstLineOnly for all logs except `kMaxLogStacks` stacks at the highest severity + if (level > this.hideStacksBelowSeverity) { + this.logLinesAtCurrentSeverity = 0; + this.hideStacksBelowSeverity = level; + + // Go back and setFirstLineOnly for everything of a lower log level + for (const log of this.logs) { + log.setStackHidden('below max severity'); + } + } + if (level === this.hideStacksBelowSeverity) { + this.logLinesAtCurrentSeverity++; + } else if (level < kMinSeverityForStack) { + logMessage.setStackHidden(''); + } else if (level < this.hideStacksBelowSeverity) { + logMessage.setStackHidden('below max severity'); + } + if (this.logLinesAtCurrentSeverity > kMaxLogStacks) { + logMessage.setStackHidden(`only ${kMaxLogStacks} shown`); + } + + this.logs.push(logMessage); + } +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/params_utils.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/params_utils.ts new file mode 100644 index 0000000000..07d2f836f1 --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/params_utils.ts @@ -0,0 +1,124 @@ +import { TestParams } from '../framework/fixture.js'; +import { ResolveType, UnionToIntersection } from '../util/types.js'; +import { assert } from '../util/util.js'; + +import { comparePublicParamsPaths, Ordering } from './query/compare.js'; +import { kWildcard, kParamSeparator, kParamKVSeparator } from './query/separators.js'; + +export type JSONWithUndefined = + | undefined + | null + | number + | string + | boolean + | readonly JSONWithUndefined[] + // Ideally this would recurse into JSONWithUndefined, but it breaks code. + | { readonly [k: string]: unknown }; +export interface TestParamsRW { + [k: string]: JSONWithUndefined; +} +export type TestParamsIterable = Iterable; + +export function paramKeyIsPublic(key: string): boolean { + return !key.startsWith('_'); +} + +export function extractPublicParams(params: TestParams): TestParams { + const publicParams: TestParamsRW = {}; + for (const k of Object.keys(params)) { + if (paramKeyIsPublic(k)) { + publicParams[k] = params[k]; + } + } + return publicParams; +} + +export const badParamValueChars = new RegExp( + '[' + kParamKVSeparator + kParamSeparator + kWildcard + ']' +); + +export function publicParamsEquals(x: TestParams, y: TestParams): boolean { + return comparePublicParamsPaths(x, y) === Ordering.Equal; +} + +export type KeyOfNeverable = T extends never ? never : keyof T; +export type AllKeysFromUnion = keyof T | KeyOfNeverable>; +export type KeyOfOr = K extends keyof T ? T[K] : Default; + +/** + * Flatten a union of interfaces into a single interface encoding the same type. + * + * Flattens a union in such a way that: + * `{ a: number, b?: undefined } | { b: string, a?: undefined }` + * (which is the value type of `[{ a: 1 }, { b: 1 }]`) + * becomes `{ a: number | undefined, b: string | undefined }`. + * + * And also works for `{ a: number } | { b: string }` which maps to the same. + */ +export type FlattenUnionOfInterfaces = { + [K in AllKeysFromUnion]: KeyOfOr< + T, + // If T always has K, just take T[K] (union of C[K] for each component C of T): + K, + // Otherwise, take the union of C[K] for each component C of T, PLUS undefined: + undefined | KeyOfOr, K, void> + >; +}; + +/* eslint-disable-next-line @typescript-eslint/no-unused-vars */ +function typeAssert() {} +{ + type Test = [T] extends [U] + ? [U] extends [T] + ? 'pass' + : { actual: ResolveType; expected: U } + : { actual: ResolveType; expected: U }; + + type T01 = { a: number } | { b: string }; + type T02 = { a: number } | { b?: string }; + type T03 = { a: number } | { a?: number }; + type T04 = { a: number } | { a: string }; + type T05 = { a: number } | { a?: string }; + + type T11 = { a: number; b?: undefined } | { a?: undefined; b: string }; + + type T21 = { a: number; b?: undefined } | { b: string }; + type T22 = { a: number; b?: undefined } | { b?: string }; + type T23 = { a: number; b?: undefined } | { a?: number }; + type T24 = { a: number; b?: undefined } | { a: string }; + type T25 = { a: number; b?: undefined } | { a?: string }; + type T26 = { a: number; b?: undefined } | { a: undefined }; + type T27 = { a: number; b?: undefined } | { a: undefined; b: undefined }; + + /* prettier-ignore */ { + typeAssert, { a: number | undefined; b: string | undefined }>>(); + typeAssert, { a: number | undefined; b: string | undefined }>>(); + typeAssert, { a: number | undefined }>>(); + typeAssert, { a: number | string }>>(); + typeAssert, { a: number | string | undefined }>>(); + + typeAssert, { a: number | undefined; b: string | undefined }>>(); + + typeAssert, { a: number | undefined; b: string | undefined }>>(); + typeAssert, { a: number | undefined; b: undefined }>>(); + typeAssert, { a: number | string; b: undefined }>>(); + typeAssert, { a: number | string | undefined; b: undefined }>>(); + typeAssert, { a: number | undefined; b: undefined }>>(); + + // Unexpected test results - hopefully okay to ignore these + typeAssert, { b: string | undefined }>>(); + typeAssert, { a: number | undefined }>>(); + } +} + +export type Merged = MergedFromFlat>; +export type MergedFromFlat = { + [K in keyof A | keyof B]: K extends keyof B ? B[K] : K extends keyof A ? A[K] : never; +}; + +export function mergeParams(a: A, b: B): Merged { + for (const key of Object.keys(a)) { + assert(!(key in b), 'Duplicate key: ' + key); + } + return { ...a, ...b } as Merged; +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/query/compare.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/query/compare.ts new file mode 100644 index 0000000000..e9f4b01503 --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/query/compare.ts @@ -0,0 +1,94 @@ +import { TestParams } from '../../framework/fixture.js'; +import { assert, objectEquals } from '../../util/util.js'; +import { paramKeyIsPublic } from '../params_utils.js'; + +import { TestQuery } from './query.js'; + +export const enum Ordering { + Unordered, + StrictSuperset, + Equal, + StrictSubset, +} + +/** + * Compares two queries for their ordering (which is used to build the tree). + * + * See src/unittests/query_compare.spec.ts for examples. + */ +export function compareQueries(a: TestQuery, b: TestQuery): Ordering { + if (a.suite !== b.suite) { + return Ordering.Unordered; + } + + const filePathOrdering = comparePaths(a.filePathParts, b.filePathParts); + if (filePathOrdering !== Ordering.Equal || a.isMultiFile || b.isMultiFile) { + return compareOneLevel(filePathOrdering, a.isMultiFile, b.isMultiFile); + } + assert('testPathParts' in a && 'testPathParts' in b); + + const testPathOrdering = comparePaths(a.testPathParts, b.testPathParts); + if (testPathOrdering !== Ordering.Equal || a.isMultiTest || b.isMultiTest) { + return compareOneLevel(testPathOrdering, a.isMultiTest, b.isMultiTest); + } + assert('params' in a && 'params' in b); + + const paramsPathOrdering = comparePublicParamsPaths(a.params, b.params); + if (paramsPathOrdering !== Ordering.Equal || a.isMultiCase || b.isMultiCase) { + return compareOneLevel(paramsPathOrdering, a.isMultiCase, b.isMultiCase); + } + return Ordering.Equal; +} + +/** + * Compares a single level of a query. + * + * "IsBig" means the query is big relative to the level, e.g. for test-level: + * - Anything >= `suite:a,*` is big + * - Anything <= `suite:a:*` is small + */ +function compareOneLevel(ordering: Ordering, aIsBig: boolean, bIsBig: boolean): Ordering { + assert(ordering !== Ordering.Equal || aIsBig || bIsBig); + if (ordering === Ordering.Unordered) return Ordering.Unordered; + if (aIsBig && bIsBig) return ordering; + if (!aIsBig && !bIsBig) return Ordering.Unordered; // Equal case is already handled + // Exactly one of (a, b) is big. + if (aIsBig && ordering !== Ordering.StrictSubset) return Ordering.StrictSuperset; + if (bIsBig && ordering !== Ordering.StrictSuperset) return Ordering.StrictSubset; + return Ordering.Unordered; +} + +function comparePaths(a: readonly string[], b: readonly string[]): Ordering { + const shorter = Math.min(a.length, b.length); + + for (let i = 0; i < shorter; ++i) { + if (a[i] !== b[i]) { + return Ordering.Unordered; + } + } + if (a.length === b.length) { + return Ordering.Equal; + } else if (a.length < b.length) { + return Ordering.StrictSuperset; + } else { + return Ordering.StrictSubset; + } +} + +export function comparePublicParamsPaths(a: TestParams, b: TestParams): Ordering { + const aKeys = Object.keys(a).filter(k => paramKeyIsPublic(k)); + const commonKeys = new Set(aKeys.filter(k => k in b)); + + for (const k of commonKeys) { + if (!objectEquals(a[k], b[k])) { + return Ordering.Unordered; + } + } + const bKeys = Object.keys(b).filter(k => paramKeyIsPublic(k)); + const aRemainingKeys = aKeys.length - commonKeys.size; + const bRemainingKeys = bKeys.length - commonKeys.size; + if (aRemainingKeys === 0 && bRemainingKeys === 0) return Ordering.Equal; + if (aRemainingKeys === 0) return Ordering.StrictSuperset; + if (bRemainingKeys === 0) return Ordering.StrictSubset; + return Ordering.Unordered; +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/query/encode_selectively.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/query/encode_selectively.ts new file mode 100644 index 0000000000..ab1997b6e4 --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/query/encode_selectively.ts @@ -0,0 +1,23 @@ +/** + * Encodes a stringified TestQuery so that it can be placed in a `?q=` parameter in a URL. + * + * `encodeURIComponent` encodes in accordance with `application/x-www-form-urlencoded`, + * but URLs don't actually have to be as strict as HTML form encoding + * (we interpret this purely from JavaScript). + * So we encode the component, then selectively convert some %-encoded escape codes + * back to their original form for readability/copyability. + */ +export function encodeURIComponentSelectively(s: string): string { + let ret = encodeURIComponent(s); + ret = ret.replace(/%22/g, '"'); // for JSON strings + ret = ret.replace(/%2C/g, ','); // for path separator, and JSON arrays + ret = ret.replace(/%3A/g, ':'); // for big separator + ret = ret.replace(/%3B/g, ';'); // for param separator + ret = ret.replace(/%3D/g, '='); // for params (k=v) + ret = ret.replace(/%5B/g, '['); // for JSON arrays + ret = ret.replace(/%5D/g, ']'); // for JSON arrays + ret = ret.replace(/%7B/g, '{'); // for JSON objects + ret = ret.replace(/%7D/g, '}'); // for JSON objects + ret = ret.replace(/%E2%9C%97/g, '✗'); // for jsUndefinedMagicValue + return ret; +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/query/json_param_value.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/query/json_param_value.ts new file mode 100644 index 0000000000..f4be7642d3 --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/query/json_param_value.ts @@ -0,0 +1,83 @@ +import { assert, sortObjectByKey } from '../../util/util.js'; +import { JSONWithUndefined } from '../params_utils.js'; + +// JSON can't represent various values and by default stores them as `null`. +// Instead, storing them as a magic string values in JSON. +const jsUndefinedMagicValue = '_undef_'; +const jsNaNMagicValue = '_nan_'; +const jsPositiveInfinityMagicValue = '_posinfinity_'; +const jsNegativeInfinityMagicValue = '_neginfinity_'; + +// -0 needs to be handled separately, because -0 === +0 returns true. Not +// special casing +0/0, since it behaves intuitively. Assuming that if -0 is +// being used, the differentiation from +0 is desired. +const jsNegativeZeroMagicValue = '_negzero_'; + +const toStringMagicValue = new Map([ + [undefined, jsUndefinedMagicValue], + [NaN, jsNaNMagicValue], + [Number.POSITIVE_INFINITY, jsPositiveInfinityMagicValue], + [Number.NEGATIVE_INFINITY, jsNegativeInfinityMagicValue], + // No -0 handling because it is special cased. +]); + +const fromStringMagicValue = new Map([ + [jsUndefinedMagicValue, undefined], + [jsNaNMagicValue, NaN], + [jsPositiveInfinityMagicValue, Number.POSITIVE_INFINITY], + [jsNegativeInfinityMagicValue, Number.NEGATIVE_INFINITY], + // -0 is handled in this direction because there is no comparison issue. + [jsNegativeZeroMagicValue, -0], +]); + +function stringifyFilter(k: string, v: unknown): unknown { + // Make sure no one actually uses a magic value as a parameter. + if (typeof v === 'string') { + assert( + !fromStringMagicValue.has(v), + `${v} is a magic value for stringification, so cannot be used` + ); + + assert( + v !== jsNegativeZeroMagicValue, + `${v} is a magic value for stringification, so cannot be used` + ); + } + + if (Object.is(v, -0)) { + return jsNegativeZeroMagicValue; + } + + return toStringMagicValue.has(v) ? toStringMagicValue.get(v) : v; +} + +export function stringifyParamValue(value: JSONWithUndefined): string { + return JSON.stringify(value, stringifyFilter); +} + +/** + * Like stringifyParamValue but sorts dictionaries by key, for hashing. + */ +export function stringifyParamValueUniquely(value: JSONWithUndefined): string { + return JSON.stringify(value, (k, v) => { + if (typeof v === 'object' && v !== null) { + return sortObjectByKey(v); + } + + return stringifyFilter(k, v); + }); +} + +// 'any' is part of the JSON.parse reviver interface, so cannot be avoided. +// eslint-disable-next-line @typescript-eslint/no-explicit-any +function parseParamValueReviver(k: string, v: any): any { + if (fromStringMagicValue.has(v)) { + return fromStringMagicValue.get(v); + } + + return v; +} + +export function parseParamValue(s: string): JSONWithUndefined { + return JSON.parse(s, parseParamValueReviver); +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/query/parseQuery.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/query/parseQuery.ts new file mode 100644 index 0000000000..996835b0ec --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/query/parseQuery.ts @@ -0,0 +1,155 @@ +import { assert } from '../../util/util.js'; +import { + TestParamsRW, + JSONWithUndefined, + badParamValueChars, + paramKeyIsPublic, +} from '../params_utils.js'; + +import { parseParamValue } from './json_param_value.js'; +import { + TestQuery, + TestQueryMultiFile, + TestQueryMultiTest, + TestQueryMultiCase, + TestQuerySingleCase, +} from './query.js'; +import { kBigSeparator, kWildcard, kPathSeparator, kParamSeparator } from './separators.js'; +import { validQueryPart } from './validQueryPart.js'; + +export function parseQuery(s: string): TestQuery { + try { + return parseQueryImpl(s); + } catch (ex) { + if (ex instanceof Error) { + ex.message += '\n on: ' + s; + } + throw ex; + } +} + +function parseQueryImpl(s: string): TestQuery { + // Undo encodeURIComponentSelectively + s = decodeURIComponent(s); + + // bigParts are: suite, file, test, params (note kBigSeparator could appear in params) + let suite: string; + let fileString: string | undefined; + let testString: string | undefined; + let paramsString: string | undefined; + { + const i1 = s.indexOf(kBigSeparator); + assert(i1 !== -1, `query string must have at least one ${kBigSeparator}`); + suite = s.substring(0, i1); + const i2 = s.indexOf(kBigSeparator, i1 + 1); + if (i2 === -1) { + fileString = s.substring(i1 + 1); + } else { + fileString = s.substring(i1 + 1, i2); + const i3 = s.indexOf(kBigSeparator, i2 + 1); + if (i3 === -1) { + testString = s.substring(i2 + 1); + } else { + testString = s.substring(i2 + 1, i3); + paramsString = s.substring(i3 + 1); + } + } + } + + const { parts: file, wildcard: filePathHasWildcard } = parseBigPart(fileString, kPathSeparator); + + if (testString === undefined) { + // Query is file-level + assert( + filePathHasWildcard, + `File-level query without wildcard ${kWildcard}. Did you want a file-level query \ +(append ${kPathSeparator}${kWildcard}) or test-level query (append ${kBigSeparator}${kWildcard})?` + ); + return new TestQueryMultiFile(suite, file); + } + assert(!filePathHasWildcard, `Wildcard ${kWildcard} must be at the end of the query string`); + + const { parts: test, wildcard: testPathHasWildcard } = parseBigPart(testString, kPathSeparator); + + if (paramsString === undefined) { + // Query is test-level + assert( + testPathHasWildcard, + `Test-level query without wildcard ${kWildcard}; did you want a test-level query \ +(append ${kPathSeparator}${kWildcard}) or case-level query (append ${kBigSeparator}${kWildcard})?` + ); + assert(file.length > 0, 'File part of test-level query was empty (::)'); + return new TestQueryMultiTest(suite, file, test); + } + + // Query is case-level + assert(!testPathHasWildcard, `Wildcard ${kWildcard} must be at the end of the query string`); + + const { parts: paramsParts, wildcard: paramsHasWildcard } = parseBigPart( + paramsString, + kParamSeparator + ); + + assert(test.length > 0, 'Test part of case-level query was empty (::)'); + + const params: TestParamsRW = {}; + for (const paramPart of paramsParts) { + const [k, v] = parseSingleParam(paramPart); + assert(validQueryPart.test(k), `param key names must match ${validQueryPart}`); + params[k] = v; + } + if (paramsHasWildcard) { + return new TestQueryMultiCase(suite, file, test, params); + } else { + return new TestQuerySingleCase(suite, file, test, params); + } +} + +// webgpu:a,b,* or webgpu:a,b,c:* +const kExampleQueries = `\ +webgpu${kBigSeparator}a${kPathSeparator}b${kPathSeparator}${kWildcard} or \ +webgpu${kBigSeparator}a${kPathSeparator}b${kPathSeparator}c${kBigSeparator}${kWildcard}`; + +function parseBigPart( + s: string, + separator: typeof kParamSeparator | typeof kPathSeparator +): { parts: string[]; wildcard: boolean } { + if (s === '') { + return { parts: [], wildcard: false }; + } + const parts = s.split(separator); + + let endsWithWildcard = false; + for (const [i, part] of parts.entries()) { + if (i === parts.length - 1) { + endsWithWildcard = part === kWildcard; + } + assert( + part.indexOf(kWildcard) === -1 || endsWithWildcard, + `Wildcard ${kWildcard} must be complete last part of a path (e.g. ${kExampleQueries})` + ); + } + if (endsWithWildcard) { + // Remove the last element of the array (which is just the wildcard). + parts.length = parts.length - 1; + } + return { parts, wildcard: endsWithWildcard }; +} + +function parseSingleParam(paramSubstring: string): [string, JSONWithUndefined] { + assert(paramSubstring !== '', 'Param in a query must not be blank (is there a trailing comma?)'); + const i = paramSubstring.indexOf('='); + assert(i !== -1, 'Param in a query must be of form key=value'); + const k = paramSubstring.substring(0, i); + assert(paramKeyIsPublic(k), 'Param in a query must not be private (start with _)'); + const v = paramSubstring.substring(i + 1); + return [k, parseSingleParamValue(v)]; +} + +function parseSingleParamValue(s: string): JSONWithUndefined { + assert( + !badParamValueChars.test(s), + `param value must not match ${badParamValueChars} - was ${s}` + ); + return parseParamValue(s); +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/query/query.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/query/query.ts new file mode 100644 index 0000000000..59e96cb538 --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/query/query.ts @@ -0,0 +1,262 @@ +import { TestParams } from '../../framework/fixture.js'; +import { optionEnabled } from '../../runtime/helper/options.js'; +import { assert, unreachable } from '../../util/util.js'; +import { Expectation } from '../logging/result.js'; + +import { compareQueries, Ordering } from './compare.js'; +import { encodeURIComponentSelectively } from './encode_selectively.js'; +import { parseQuery } from './parseQuery.js'; +import { kBigSeparator, kPathSeparator, kWildcard } from './separators.js'; +import { stringifyPublicParams } from './stringify_params.js'; + +/** + * Represents a test query of some level. + * + * TestQuery types are immutable. + */ +export type TestQuery = + | TestQuerySingleCase + | TestQueryMultiCase + | TestQueryMultiTest + | TestQueryMultiFile; + +/** + * - 1 = MultiFile. + * - 2 = MultiTest. + * - 3 = MultiCase. + * - 4 = SingleCase. + */ +export type TestQueryLevel = 1 | 2 | 3 | 4; + +export interface TestQueryWithExpectation { + query: TestQuery; + expectation: Expectation; +} + +/** + * A multi-file test query, like `s:*` or `s:a,b,*`. + * + * Immutable (makes copies of constructor args). + */ +export class TestQueryMultiFile { + readonly level: TestQueryLevel = 1; + readonly isMultiFile: boolean = true; + readonly suite: string; + readonly filePathParts: readonly string[]; + + constructor(suite: string, file: readonly string[]) { + this.suite = suite; + this.filePathParts = [...file]; + } + + get depthInLevel() { + return this.filePathParts.length; + } + + toString(): string { + return encodeURIComponentSelectively(this.toStringHelper().join(kBigSeparator)); + } + + protected toStringHelper(): string[] { + return [this.suite, [...this.filePathParts, kWildcard].join(kPathSeparator)]; + } +} + +/** + * A multi-test test query, like `s:f:*` or `s:f:a,b,*`. + * + * Immutable (makes copies of constructor args). + */ +export class TestQueryMultiTest extends TestQueryMultiFile { + readonly level: TestQueryLevel = 2; + readonly isMultiFile: false = false; + readonly isMultiTest: boolean = true; + readonly testPathParts: readonly string[]; + + constructor(suite: string, file: readonly string[], test: readonly string[]) { + super(suite, file); + assert(file.length > 0, 'multi-test (or finer) query must have file-path'); + this.testPathParts = [...test]; + } + + get depthInLevel() { + return this.testPathParts.length; + } + + protected toStringHelper(): string[] { + return [ + this.suite, + this.filePathParts.join(kPathSeparator), + [...this.testPathParts, kWildcard].join(kPathSeparator), + ]; + } +} + +/** + * A multi-case test query, like `s:f:t:*` or `s:f:t:a,b,*`. + * + * Immutable (makes copies of constructor args), except for param values + * (which aren't normally supposed to change; they're marked readonly in TestParams). + */ +export class TestQueryMultiCase extends TestQueryMultiTest { + readonly level: TestQueryLevel = 3; + readonly isMultiTest: false = false; + readonly isMultiCase: boolean = true; + readonly params: TestParams; + + constructor(suite: string, file: readonly string[], test: readonly string[], params: TestParams) { + super(suite, file, test); + assert(test.length > 0, 'multi-case (or finer) query must have test-path'); + this.params = { ...params }; + } + + get depthInLevel() { + return Object.keys(this.params).length; + } + + protected toStringHelper(): string[] { + return [ + this.suite, + this.filePathParts.join(kPathSeparator), + this.testPathParts.join(kPathSeparator), + stringifyPublicParams(this.params, true), + ]; + } +} + +/** + * A multi-case test query, like `s:f:t:` or `s:f:t:a=1,b=1`. + * + * Immutable (makes copies of constructor args). + */ +export class TestQuerySingleCase extends TestQueryMultiCase { + readonly level: TestQueryLevel = 4; + readonly isMultiCase: false = false; + + get depthInLevel() { + return 0; + } + + protected toStringHelper(): string[] { + return [ + this.suite, + this.filePathParts.join(kPathSeparator), + this.testPathParts.join(kPathSeparator), + stringifyPublicParams(this.params), + ]; + } +} + +/** + * Parse raw expectations input into TestQueryWithExpectation[], filtering so that only + * expectations that are relevant for the provided query and wptURL. + * + * `rawExpectations` should be @type {{ query: string, expectation: Expectation }[]} + * + * The `rawExpectations` are parsed and validated that they are in the correct format. + * If `wptURL` is passed, the query string should be of the full path format such + * as `path/to/cts.https.html?worker=0&q=suite:test_path:test_name:foo=1;bar=2;*`. + * If `wptURL` is `undefined`, the query string should be only the query + * `suite:test_path:test_name:foo=1;bar=2;*`. + */ +export function parseExpectationsForTestQuery( + rawExpectations: + | unknown + | { + query: string; + expectation: Expectation; + }[], + query: TestQuery, + wptURL?: URL +) { + if (!Array.isArray(rawExpectations)) { + unreachable('Expectations should be an array'); + } + const expectations: TestQueryWithExpectation[] = []; + for (const entry of rawExpectations) { + assert(typeof entry === 'object'); + const rawExpectation = entry as { query?: string; expectation?: string }; + assert(rawExpectation.query !== undefined, 'Expectation missing query string'); + assert(rawExpectation.expectation !== undefined, 'Expectation missing expectation string'); + + let expectationQuery: TestQuery; + if (wptURL !== undefined) { + const expectationURL = new URL(`${wptURL.origin}/${entry.query}`); + if (expectationURL.pathname !== wptURL.pathname) { + continue; + } + assert( + expectationURL.pathname === wptURL.pathname, + `Invalid expectation path ${expectationURL.pathname} +Expectation should be of the form path/to/cts.https.html?worker=0&q=suite:test_path:test_name:foo=1;bar=2;... + ` + ); + + const params = expectationURL.searchParams; + if (optionEnabled('worker', params) !== optionEnabled('worker', wptURL.searchParams)) { + continue; + } + + const qs = params.getAll('q'); + assert(qs.length === 1, 'currently, there must be exactly one ?q= in the expectation string'); + expectationQuery = parseQuery(qs[0]); + } else { + expectationQuery = parseQuery(entry.query); + } + + // Strip params from multicase expectations so that an expectation of foo=2;* + // is stored if the test query is bar=3;* + const queryForFilter = + expectationQuery instanceof TestQueryMultiCase + ? new TestQueryMultiCase( + expectationQuery.suite, + expectationQuery.filePathParts, + expectationQuery.testPathParts, + {} + ) + : expectationQuery; + + if (compareQueries(query, queryForFilter) === Ordering.Unordered) { + continue; + } + + switch (entry.expectation) { + case 'pass': + case 'skip': + case 'fail': + break; + default: + unreachable(`Invalid expectation ${entry.expectation}`); + } + + expectations.push({ + query: expectationQuery, + expectation: entry.expectation, + }); + } + return expectations; +} + +/** + * For display purposes only, produces a "relative" query string from parent to child. + * Used in the wpt runtime to reduce the verbosity of logs. + */ +export function relativeQueryString(parent: TestQuery, child: TestQuery): string { + const ordering = compareQueries(parent, child); + if (ordering === Ordering.Equal) { + return ''; + } else if (ordering === Ordering.StrictSuperset) { + const parentString = parent.toString(); + assert(parentString.endsWith(kWildcard)); + const childString = child.toString(); + assert( + childString.startsWith(parentString.substring(0, parentString.length - 2)), + 'impossible?: childString does not start with parentString[:-2]' + ); + return childString.substring(parentString.length - 2); + } else { + unreachable( + `relativeQueryString arguments have invalid ordering ${ordering}:\n${parent}\n${child}` + ); + } +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/query/separators.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/query/separators.ts new file mode 100644 index 0000000000..0c8f6ea9a9 --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/query/separators.ts @@ -0,0 +1,14 @@ +/** Separator between big parts: suite:file:test:case */ +export const kBigSeparator = ':'; + +/** Separator between path,to,file or path,to,test */ +export const kPathSeparator = ','; + +/** Separator between k=v;k=v */ +export const kParamSeparator = ';'; + +/** Separator between key and value in k=v */ +export const kParamKVSeparator = '='; + +/** Final wildcard, if query is not single-case */ +export const kWildcard = '*'; diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/query/stringify_params.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/query/stringify_params.ts new file mode 100644 index 0000000000..907cc0791a --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/query/stringify_params.ts @@ -0,0 +1,44 @@ +import { TestParams } from '../../framework/fixture.js'; +import { assert } from '../../util/util.js'; +import { JSONWithUndefined, badParamValueChars, paramKeyIsPublic } from '../params_utils.js'; + +import { stringifyParamValue, stringifyParamValueUniquely } from './json_param_value.js'; +import { kParamKVSeparator, kParamSeparator, kWildcard } from './separators.js'; + +export function stringifyPublicParams(p: TestParams, addWildcard = false): string { + const parts = Object.keys(p) + .filter(k => paramKeyIsPublic(k)) + .map(k => stringifySingleParam(k, p[k])); + + if (addWildcard) parts.push(kWildcard); + + return parts.join(kParamSeparator); +} + +/** + * An _approximately_ unique string representing a CaseParams value. + */ +export function stringifyPublicParamsUniquely(p: TestParams): string { + const keys = Object.keys(p).sort(); + return keys + .filter(k => paramKeyIsPublic(k)) + .map(k => stringifySingleParamUniquely(k, p[k])) + .join(kParamSeparator); +} + +export function stringifySingleParam(k: string, v: JSONWithUndefined) { + return `${k}${kParamKVSeparator}${stringifySingleParamValue(v)}`; +} + +function stringifySingleParamUniquely(k: string, v: JSONWithUndefined) { + return `${k}${kParamKVSeparator}${stringifyParamValueUniquely(v)}`; +} + +function stringifySingleParamValue(v: JSONWithUndefined): string { + const s = stringifyParamValue(v); + assert( + !badParamValueChars.test(s), + `JSON.stringified param value must not match ${badParamValueChars} - was ${s}` + ); + return s; +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/query/validQueryPart.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/query/validQueryPart.ts new file mode 100644 index 0000000000..62184adb62 --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/query/validQueryPart.ts @@ -0,0 +1,2 @@ +/** Applies to group parts, test parts, params keys. */ +export const validQueryPart = /^[a-zA-Z0-9_]+$/; diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/stack.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/stack.ts new file mode 100644 index 0000000000..5de54088c8 --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/stack.ts @@ -0,0 +1,82 @@ +// Returns the stack trace of an Error, but without the extra boilerplate at the bottom +// (e.g. RunCaseSpecific, processTicksAndRejections, etc.), for logging. +export function extractImportantStackTrace(e: Error): string { + let stack = e.stack; + if (!stack) { + return ''; + } + const redundantMessage = 'Error: ' + e.message + '\n'; + if (stack.startsWith(redundantMessage)) { + stack = stack.substring(redundantMessage.length); + } + + const lines = stack.split('\n'); + for (let i = lines.length - 1; i >= 0; --i) { + const line = lines[i]; + if (line.indexOf('.spec.') !== -1) { + return lines.slice(0, i + 1).join('\n'); + } + } + return stack; +} + +// *** Examples *** +// +// Node fail() +// > Error: +// > at CaseRecorder.fail (/Users/kainino/src/cts/src/common/framework/logger.ts:99:30) +// > at RunCaseSpecific.exports.g.test.t [as fn] (/Users/kainino/src/cts/src/unittests/logger.spec.ts:80:7) +// x at RunCaseSpecific.run (/Users/kainino/src/cts/src/common/framework/test_group.ts:121:18) +// x at processTicksAndRejections (internal/process/task_queues.js:86:5) +// +// Node throw +// > Error: hello +// > at RunCaseSpecific.g.test.t [as fn] (/Users/kainino/src/cts/src/unittests/test_group.spec.ts:51:11) +// x at RunCaseSpecific.run (/Users/kainino/src/cts/src/common/framework/test_group.ts:121:18) +// x at processTicksAndRejections (internal/process/task_queues.js:86:5) +// +// Firefox fail() +// > fail@http://localhost:8080/out/framework/logger.js:104:30 +// > expect@http://localhost:8080/out/framework/default_fixture.js:59:16 +// > @http://localhost:8080/out/unittests/util.spec.js:35:5 +// x run@http://localhost:8080/out/framework/test_group.js:119:18 +// +// Firefox throw +// > @http://localhost:8080/out/unittests/test_group.spec.js:48:11 +// x run@http://localhost:8080/out/framework/test_group.js:119:18 +// +// Safari fail() +// > fail@http://localhost:8080/out/framework/logger.js:104:39 +// > expect@http://localhost:8080/out/framework/default_fixture.js:59:20 +// > http://localhost:8080/out/unittests/util.spec.js:35:11 +// x http://localhost:8080/out/framework/test_group.js:119:20 +// x asyncFunctionResume@[native code] +// x [native code] +// x promiseReactionJob@[native code] +// +// Safari throw +// > http://localhost:8080/out/unittests/test_group.spec.js:48:20 +// x http://localhost:8080/out/framework/test_group.js:119:20 +// x asyncFunctionResume@[native code] +// x [native code] +// x promiseReactionJob@[native code] +// +// Chrome fail() +// x Error +// x at CaseRecorder.fail (http://localhost:8080/out/framework/logger.js:104:30) +// x at DefaultFixture.expect (http://localhost:8080/out/framework/default_fixture.js:59:16) +// > at RunCaseSpecific.fn (http://localhost:8080/out/unittests/util.spec.js:35:5) +// x at RunCaseSpecific.run (http://localhost:8080/out/framework/test_group.js:119:18) +// x at async runCase (http://localhost:8080/out/runtime/standalone.js:37:17) +// x at async http://localhost:8080/out/runtime/standalone.js:102:7 +// +// Chrome throw +// x Error: hello +// > at RunCaseSpecific.fn (http://localhost:8080/out/unittests/test_group.spec.js:48:11) +// x at RunCaseSpecific.run (http://localhost:8080/out/framework/test_group.js:119:18)" +// x at async Promise.all (index 0) +// x at async TestGroupTest.run (http://localhost:8080/out/unittests/test_group_test.js:6:5) +// x at async RunCaseSpecific.fn (http://localhost:8080/out/unittests/test_group.spec.js:53:15) +// x at async RunCaseSpecific.run (http://localhost:8080/out/framework/test_group.js:119:7) +// x at async runCase (http://localhost:8080/out/runtime/standalone.js:37:17) +// x at async http://localhost:8080/out/runtime/standalone.js:102:7 diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/test_group.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/test_group.ts new file mode 100644 index 0000000000..63f017083c --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/test_group.ts @@ -0,0 +1,646 @@ +import { + Fixture, + SubcaseBatchState, + SkipTestCase, + TestParams, + UnexpectedPassError, +} from '../framework/fixture.js'; +import { + CaseParamsBuilder, + builderIterateCasesWithSubcases, + kUnitCaseParamsBuilder, + ParamsBuilderBase, + SubcaseParamsBuilder, +} from '../framework/params_builder.js'; +import { globalTestConfig } from '../framework/test_config.js'; +import { Expectation } from '../internal/logging/result.js'; +import { TestCaseRecorder } from '../internal/logging/test_case_recorder.js'; +import { extractPublicParams, Merged, mergeParams } from '../internal/params_utils.js'; +import { compareQueries, Ordering } from '../internal/query/compare.js'; +import { TestQuerySingleCase, TestQueryWithExpectation } from '../internal/query/query.js'; +import { kPathSeparator } from '../internal/query/separators.js'; +import { + stringifyPublicParams, + stringifyPublicParamsUniquely, +} from '../internal/query/stringify_params.js'; +import { validQueryPart } from '../internal/query/validQueryPart.js'; +import { assert, unreachable } from '../util/util.js'; + +export type RunFn = ( + rec: TestCaseRecorder, + expectations?: TestQueryWithExpectation[] +) => Promise; + +export interface TestCaseID { + readonly test: readonly string[]; + readonly params: TestParams; +} + +export interface RunCase { + readonly id: TestCaseID; + readonly isUnimplemented: boolean; + run( + rec: TestCaseRecorder, + selfQuery: TestQuerySingleCase, + expectations: TestQueryWithExpectation[] + ): Promise; +} + +// Interface for defining tests +export interface TestGroupBuilder> { + test(name: string): TestBuilderWithName; +} +export function makeTestGroup>( + fixture: FixtureClass +): TestGroupBuilder { + return new TestGroup((fixture as unknown) as FixtureClass); +} + +// Interfaces for running tests +export interface IterableTestGroup { + iterate(): Iterable; + validate(): void; +} +export interface IterableTest { + testPath: string[]; + description: string | undefined; + readonly testCreationStack: Error; + iterate(): Iterable; +} + +export function makeTestGroupForUnitTesting( + fixture: FixtureClass +): TestGroup { + return new TestGroup(fixture); +} + +export type FixtureClass< + S extends SubcaseBatchState = SubcaseBatchState, + F extends Fixture = Fixture +> = { + new (sharedState: S, log: TestCaseRecorder, params: TestParams): F; + MakeSharedState(params: TestParams): S; +}; +type TestFn = (t: F & { params: P }) => Promise | void; +type BeforeAllSubcasesFn = ( + s: S & { params: P } +) => Promise | void; + +export class TestGroup> + implements TestGroupBuilder { + private fixture: FixtureClass; + private seen: Set = new Set(); + private tests: Array> = []; + + constructor(fixture: FixtureClass) { + this.fixture = fixture; + } + + iterate(): Iterable { + return this.tests; + } + + private checkName(name: string): void { + assert( + // Shouldn't happen due to the rule above. Just makes sure that treating + // unencoded strings as encoded strings is OK. + name === decodeURIComponent(name), + `Not decodeURIComponent-idempotent: ${name} !== ${decodeURIComponent(name)}` + ); + assert(!this.seen.has(name), `Duplicate test name: ${name}`); + + this.seen.add(name); + } + + test(name: string): TestBuilderWithName { + const testCreationStack = new Error(`Test created: ${name}`); + + this.checkName(name); + + const parts = name.split(kPathSeparator); + for (const p of parts) { + assert(validQueryPart.test(p), `Invalid test name part ${p}; must match ${validQueryPart}`); + } + + const test = new TestBuilder(parts, this.fixture, testCreationStack); + this.tests.push(test); + return (test as unknown) as TestBuilderWithName; + } + + validate(): void { + for (const test of this.tests) { + test.validate(); + } + } +} + +interface TestBuilderWithName> + extends TestBuilderWithParams { + desc(description: string): this; + /** + * A noop function to associate a test with the relevant part of the specification. + * + * @param url a link to the spec where test is extracted from. + */ + specURL(url: string): this; + /** + * Parameterize the test, generating multiple cases, each possibly having subcases. + * + * The `unit` value passed to the `cases` callback is an immutable constant + * `CaseParamsBuilder<{}>` representing the "unit" builder `[ {} ]`, + * provided for convenience. The non-callback overload can be used if `unit` is not needed. + */ + params( + cases: (unit: CaseParamsBuilder<{}>) => ParamsBuilderBase + ): TestBuilderWithParams; + /** + * Parameterize the test, generating multiple cases, each possibly having subcases. + * + * Use the callback overload of this method if a "unit" builder is needed. + */ + params( + cases: ParamsBuilderBase + ): TestBuilderWithParams; + + /** + * Parameterize the test, generating multiple cases, without subcases. + */ + paramsSimple

(cases: Iterable

): TestBuilderWithParams; + + /** + * Parameterize the test, generating one case with multiple subcases. + */ + paramsSubcasesOnly

(subcases: Iterable

): TestBuilderWithParams; + /** + * Parameterize the test, generating one case with multiple subcases. + * + * The `unit` value passed to the `subcases` callback is an immutable constant + * `SubcaseParamsBuilder<{}>`, with one empty case `{}` and one empty subcase `{}`. + */ + paramsSubcasesOnly

( + subcases: (unit: SubcaseParamsBuilder<{}, {}>) => SubcaseParamsBuilder<{}, P> + ): TestBuilderWithParams; +} + +interface TestBuilderWithParams< + S extends SubcaseBatchState, + F extends Fixture, + CaseP extends {}, + SubcaseP extends {} +> { + /** + * Limit subcases to a maximum number of per testcase. + * @param b the maximum number of subcases per testcase. + * + * If the number of subcases exceeds `b`, add an internal + * numeric, incrementing `batch__` param to split subcases + * into groups of at most `b` subcases. + */ + batch(b: number): this; + /** + * Run a function on shared subcase batch state before each + * batch of subcases. + * @param fn the function to run. It is called with the test + * fixture's shared subcase batch state. + * + * Generally, this function should be careful to avoid mutating + * any state on the shared subcase batch state which could result + * in unexpected order-dependent test behavior. + */ + beforeAllSubcases(fn: BeforeAllSubcasesFn): this; + /** + * Set the test function. + * @param fn the test function. + */ + fn(fn: TestFn>): void; + /** + * Mark the test as unimplemented. + */ + unimplemented(): void; +} + +class TestBuilder { + readonly testPath: string[]; + isUnimplemented: boolean; + description: string | undefined; + readonly testCreationStack: Error; + + private readonly fixture: FixtureClass; + private testFn: TestFn | undefined; + private beforeFn: BeforeAllSubcasesFn | undefined; + private testCases?: ParamsBuilderBase<{}, {}> = undefined; + private batchSize: number = 0; + + constructor(testPath: string[], fixture: FixtureClass, testCreationStack: Error) { + this.testPath = testPath; + this.isUnimplemented = false; + this.fixture = fixture; + this.testCreationStack = testCreationStack; + } + + desc(description: string): this { + this.description = description.trim(); + return this; + } + + specURL(url: string): this { + return this; + } + + beforeAllSubcases(fn: BeforeAllSubcasesFn): this { + assert(this.beforeFn === undefined); + this.beforeFn = fn; + return this; + } + + fn(fn: TestFn): void { + // eslint-disable-next-line no-warning-comments + // MAINTENANCE_TODO: add "TODO" if there's no description? (and make sure it only ends up on + // actual tests, not on test parents in the tree, which is what happens if you do it here, not + // sure why) + assert(this.testFn === undefined); + this.testFn = fn; + } + + batch(b: number): this { + this.batchSize = b; + return this; + } + + unimplemented(): void { + assert(this.testFn === undefined); + + this.description = + (this.description ? this.description + '\n\n' : '') + 'TODO: .unimplemented()'; + this.isUnimplemented = true; + + this.testFn = () => { + throw new SkipTestCase('test unimplemented'); + }; + } + + validate(): void { + const testPathString = this.testPath.join(kPathSeparator); + assert(this.testFn !== undefined, () => { + let s = `Test is missing .fn(): ${testPathString}`; + if (this.testCreationStack.stack) { + s += `\n-> test created at:\n${this.testCreationStack.stack}`; + } + return s; + }); + + if (this.testCases === undefined) { + return; + } + + const seen = new Set(); + for (const [caseParams, subcases] of builderIterateCasesWithSubcases(this.testCases)) { + for (const subcaseParams of subcases ?? [{}]) { + const params = mergeParams(caseParams, subcaseParams); + assert(this.batchSize === 0 || !('batch__' in params)); + + // stringifyPublicParams also checks for invalid params values + const testcaseString = stringifyPublicParams(params); + + // A (hopefully) unique representation of a params value. + const testcaseStringUnique = stringifyPublicParamsUniquely(params); + assert( + !seen.has(testcaseStringUnique), + `Duplicate public test case params for test ${testPathString}: ${testcaseString}` + ); + seen.add(testcaseStringUnique); + } + } + } + + params( + cases: ((unit: CaseParamsBuilder<{}>) => ParamsBuilderBase<{}, {}>) | ParamsBuilderBase<{}, {}> + ): TestBuilder { + assert(this.testCases === undefined, 'test case is already parameterized'); + if (cases instanceof Function) { + this.testCases = cases(kUnitCaseParamsBuilder); + } else { + this.testCases = cases; + } + return this; + } + + paramsSimple(cases: Iterable<{}>): TestBuilder { + assert(this.testCases === undefined, 'test case is already parameterized'); + this.testCases = kUnitCaseParamsBuilder.combineWithParams(cases); + return this; + } + + paramsSubcasesOnly( + subcases: Iterable<{}> | ((unit: SubcaseParamsBuilder<{}, {}>) => SubcaseParamsBuilder<{}, {}>) + ): TestBuilder { + if (subcases instanceof Function) { + return this.params(subcases(kUnitCaseParamsBuilder.beginSubcases())); + } else { + return this.params(kUnitCaseParamsBuilder.beginSubcases().combineWithParams(subcases)); + } + } + + *iterate(): IterableIterator { + assert(this.testFn !== undefined, 'No test function (.fn()) for test'); + this.testCases ??= kUnitCaseParamsBuilder; + for (const [caseParams, subcases] of builderIterateCasesWithSubcases(this.testCases)) { + if (this.batchSize === 0 || subcases === undefined) { + yield new RunCaseSpecific( + this.testPath, + caseParams, + this.isUnimplemented, + subcases, + this.fixture, + this.testFn, + this.beforeFn, + this.testCreationStack + ); + } else { + const subcaseArray = Array.from(subcases); + if (subcaseArray.length <= this.batchSize) { + yield new RunCaseSpecific( + this.testPath, + caseParams, + this.isUnimplemented, + subcaseArray, + this.fixture, + this.testFn, + this.beforeFn, + this.testCreationStack + ); + } else { + for (let i = 0; i < subcaseArray.length; i = i + this.batchSize) { + yield new RunCaseSpecific( + this.testPath, + { ...caseParams, batch__: i / this.batchSize }, + this.isUnimplemented, + subcaseArray.slice(i, Math.min(subcaseArray.length, i + this.batchSize)), + this.fixture, + this.testFn, + this.beforeFn, + this.testCreationStack + ); + } + } + } + } + } +} + +class RunCaseSpecific implements RunCase { + readonly id: TestCaseID; + readonly isUnimplemented: boolean; + + private readonly params: {}; + private readonly subcases: Iterable<{}> | undefined; + private readonly fixture: FixtureClass; + private readonly fn: TestFn; + private readonly beforeFn?: BeforeAllSubcasesFn; + private readonly testCreationStack: Error; + + constructor( + testPath: string[], + params: {}, + isUnimplemented: boolean, + subcases: Iterable<{}> | undefined, + fixture: FixtureClass, + fn: TestFn, + beforeFn: BeforeAllSubcasesFn | undefined, + testCreationStack: Error + ) { + this.id = { test: testPath, params: extractPublicParams(params) }; + this.isUnimplemented = isUnimplemented; + this.params = params; + this.subcases = subcases; + this.fixture = fixture; + this.fn = fn; + this.beforeFn = beforeFn; + this.testCreationStack = testCreationStack; + } + + async runTest( + rec: TestCaseRecorder, + sharedState: SubcaseBatchState, + params: TestParams, + throwSkip: boolean, + expectedStatus: Expectation + ): Promise { + try { + rec.beginSubCase(); + if (expectedStatus === 'skip') { + throw new SkipTestCase('Skipped by expectations'); + } + + const inst = new this.fixture(sharedState, rec, params); + try { + await inst.init(); + await this.fn(inst as Fixture & { params: {} }); + } finally { + // Runs as long as constructor succeeded, even if initialization or the test failed. + await inst.finalize(); + } + } catch (ex) { + // There was an exception from constructor, init, test, or finalize. + // An error from init or test may have been a SkipTestCase. + // An error from finalize may have been an eventualAsyncExpectation failure + // or unexpected validation/OOM error from the GPUDevice. + if (throwSkip && ex instanceof SkipTestCase) { + throw ex; + } + rec.threw(ex); + } finally { + try { + rec.endSubCase(expectedStatus); + } catch (ex) { + assert(ex instanceof UnexpectedPassError); + ex.message = `Testcase passed unexpectedly.`; + ex.stack = this.testCreationStack.stack; + rec.warn(ex); + } + } + } + + async run( + rec: TestCaseRecorder, + selfQuery: TestQuerySingleCase, + expectations: TestQueryWithExpectation[] + ): Promise { + const getExpectedStatus = (selfQueryWithSubParams: TestQuerySingleCase) => { + let didSeeFail = false; + for (const exp of expectations) { + const ordering = compareQueries(exp.query, selfQueryWithSubParams); + if (ordering === Ordering.Unordered || ordering === Ordering.StrictSubset) { + continue; + } + + switch (exp.expectation) { + // Skip takes precedence. If there is any expectation indicating a skip, + // signal it immediately. + case 'skip': + return 'skip'; + case 'fail': + // Otherwise, indicate that we might expect a failure. + didSeeFail = true; + break; + default: + unreachable(); + } + } + return didSeeFail ? 'fail' : 'pass'; + }; + + const { testHeartbeatCallback, maxSubcasesInFlight } = globalTestConfig; + try { + rec.start(); + const sharedState = this.fixture.MakeSharedState(this.params); + try { + await sharedState.init(); + if (this.beforeFn) { + await this.beforeFn(sharedState); + } + await sharedState.postInit(); + testHeartbeatCallback(); + + let allPreviousSubcasesFinalizedPromise: Promise = Promise.resolve(); + if (this.subcases) { + let totalCount = 0; + let skipCount = 0; + + // If there are too many subcases in flight, starting the next subcase will register + // `resolvePromiseBlockingSubcase` and wait until `subcaseFinishedCallback` is called. + let subcasesInFlight = 0; + let resolvePromiseBlockingSubcase: (() => void) | undefined = undefined; + const subcaseFinishedCallback = () => { + subcasesInFlight -= 1; + // If there is any subcase waiting on a previous subcase to finish, + // unblock it now, and clear the resolve callback. + if (resolvePromiseBlockingSubcase) { + resolvePromiseBlockingSubcase(); + resolvePromiseBlockingSubcase = undefined; + } + }; + + for (const subParams of this.subcases) { + // Make a recorder that will defer all calls until `allPreviousSubcasesFinalizedPromise` + // resolves. Waiting on `allPreviousSubcasesFinalizedPromise` ensures that + // logs from all the previous subcases have been flushed before flushing new logs. + const subcasePrefix = 'subcase: ' + stringifyPublicParams(subParams); + const subRec = new Proxy(rec, { + get: (target, k: keyof TestCaseRecorder) => { + const prop = TestCaseRecorder.prototype[k]; + if (typeof prop === 'function') { + testHeartbeatCallback(); + return function (...args: Parameters) { + void allPreviousSubcasesFinalizedPromise.then(() => { + // Prepend the subcase name to all error messages. + for (const arg of args) { + if (arg instanceof Error) { + try { + arg.message = subcasePrefix + '\n' + arg.message; + } catch { + // If that fails (e.g. on DOMException), try to put it in the stack: + let stack = subcasePrefix; + if (arg.stack) stack += '\n' + arg.stack; + try { + arg.stack = stack; + } catch { + // If that fails too, just silence it. + } + } + } + } + + // eslint-disable-next-line @typescript-eslint/no-explicit-any + const rv = (prop as any).apply(target, args); + // Because this proxy executes functions in a deferred manner, + // it should never be used for functions that need to return a value. + assert(rv === undefined); + }); + }; + } + return prop; + }, + }); + + const params = mergeParams(this.params, subParams); + const subcaseQuery = new TestQuerySingleCase( + selfQuery.suite, + selfQuery.filePathParts, + selfQuery.testPathParts, + params + ); + + // Limit the maximum number of subcases in flight. + if (subcasesInFlight >= maxSubcasesInFlight) { + await new Promise(resolve => { + // There should only be one subcase waiting at a time. + assert(resolvePromiseBlockingSubcase === undefined); + resolvePromiseBlockingSubcase = resolve; + }); + } + + subcasesInFlight += 1; + // Runs async without waiting so that subsequent subcases can start. + // All finalization steps will be waited on at the end of the testcase. + const finalizePromise = this.runTest( + subRec, + sharedState, + params, + /* throwSkip */ true, + getExpectedStatus(subcaseQuery) + ) + .then(() => { + subRec.info(new Error('OK')); + }) + .catch(ex => { + if (ex instanceof SkipTestCase) { + // Convert SkipTestCase to info messages + ex.message = 'subcase skipped: ' + ex.message; + subRec.info(ex); + ++skipCount; + } else { + // Since we are catching all error inside runTest(), this should never happen + subRec.threw(ex); + } + }) + .finally(subcaseFinishedCallback); + + allPreviousSubcasesFinalizedPromise = allPreviousSubcasesFinalizedPromise.then( + () => finalizePromise + ); + ++totalCount; + } + + // Wait for all subcases to finalize and report their results. + await allPreviousSubcasesFinalizedPromise; + + if (skipCount === totalCount) { + rec.skipped(new SkipTestCase('all subcases were skipped')); + } + } else { + await this.runTest( + rec, + sharedState, + this.params, + /* throwSkip */ false, + getExpectedStatus(selfQuery) + ); + } + } finally { + testHeartbeatCallback(); + // Runs as long as the shared state constructor succeeded, even if initialization or a test failed. + await sharedState.finalize(); + testHeartbeatCallback(); + } + } catch (ex) { + // There was an exception from sharedState/fixture constructor, init, beforeFn, or test. + // An error from beforeFn may have been SkipTestCase. + // An error from finalize may have been an eventualAsyncExpectation failure + // or unexpected validation/OOM error from the GPUDevice. + rec.threw(ex); + } finally { + rec.finish(); + } + } +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/test_suite_listing.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/test_suite_listing.ts new file mode 100644 index 0000000000..2d2b555366 --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/test_suite_listing.ts @@ -0,0 +1,15 @@ +// A listing of all specs within a single suite. This is the (awaited) type of +// `groups` in '{cts,unittests}/listing.ts' and `listing` in the auto-generated +// 'out/{cts,unittests}/listing.js' files (see tools/gen_listings). +export type TestSuiteListing = TestSuiteListingEntry[]; + +export type TestSuiteListingEntry = TestSuiteListingEntrySpec | TestSuiteListingEntryReadme; + +interface TestSuiteListingEntrySpec { + readonly file: string[]; +} + +interface TestSuiteListingEntryReadme { + readonly file: string[]; + readonly readme: string; +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/tree.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/tree.ts new file mode 100644 index 0000000000..204a4f693a --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/tree.ts @@ -0,0 +1,575 @@ +import { RunCase, RunFn } from '../internal/test_group.js'; +import { assert } from '../util/util.js'; + +import { TestFileLoader } from './file_loader.js'; +import { TestParamsRW } from './params_utils.js'; +import { 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 { + 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 }; +} + +export interface TestSubtree extends TestTreeNodeBase { + readonly children: Map; + readonly collapsible: boolean; + description?: string; + readonly testCreationStack?: Error; +} + +export interface TestTreeLeaf extends TestTreeNodeBase { + readonly run: RunFn; + readonly isUnimplemented?: boolean; + subtreeCounts?: undefined; +} + +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; + + constructor(forQuery: TestQuery, root: TestSubtree) { + this.forQuery = forQuery; + TestTree.propagateCounts(root); + this.root = root; + assert( + root.query.level === 1 && root.query.depthInLevel === 0, + 'TestTree root must be the root (suite:*)' + ); + } + + /** + * 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> { + const expandThroughLevel = Math.max(this.forQuery.level, alwaysExpandThroughLevel); + return TestTree.iterateSubtreeNodes(this.root, { + includeIntermediateNodes, + includeEmptySubtrees, + expandThroughLevel, + }); + } + + iterateLeaves(): IterableIterator> { + 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 { + 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 { + 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 propagateCounts(subtree: TestSubtree): { tests: number; nodesWithTODO: number } { + subtree.subtreeCounts ??= { tests: 0, nodesWithTODO: 0 }; + for (const [, child] of subtree.children) { + if ('children' in child) { + const counts = TestTree.propagateCounts(child); + subtree.subtreeCounts.tests += counts.tests; + subtree.subtreeCounts.nodesWithTODO += counts.nodesWithTODO; + } + } + return subtree.subtreeCounts; + } + + /** 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: TestQuery[] +): Promise { + 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; + }); + + // 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); + 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; + } + } + + 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 = addSubtreeForDirPath( + subtreeL0, + entry.file, + isCollapsible + ); + setSubtreeDescriptionAndCountTODOs(readmeSubtree, entry.readme); + continue; + } + // Entry is a spec file. + + const spec = await loader.importSpecFile(queryToLoad.suite, entry.file); + // subtreeL1 is suite:a,b:* + const subtreeL1: TestSubtree = 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 = addSubtreeForTestPath( + subtreeL1, + t.testPath, + t.testCreationStack, + isCollapsible + ); + // This is 1 test. Set tests=1 then count TODOs. + subtreeL2.subtreeCounts ??= { tests: 1, nodesWithTODO: 0 }; + if (t.description) setSubtreeDescriptionAndCountTODOs(subtreeL2, t.description); + + // 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()) { + { + const queryL3 = new TestQuerySingleCase(suite, entry.file, c.id.test, c.id.params); + const orderingL3 = compareQueries(queryL3, queryToLoad); + if (orderingL3 === Ordering.Unordered || orderingL3 === Ordering.StrictSuperset) { + // Case is not matched by this query. + 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 new TestTree(queryToLoad, subtreeL0); +} + +function setSubtreeDescriptionAndCountTODOs( + subtree: TestSubtree, + description: string +) { + assert(subtree.description === undefined); + subtree.description = description.trim(); + subtree.subtreeCounts ??= { tests: 0, nodesWithTODO: 0 }; + if (subtree.description.indexOf('TODO') !== -1) { + subtree.subtreeCounts.nodesWithTODO++; + } +} + +function makeTreeForSuite( + suite: string, + isCollapsible: (sq: TestQuery) => boolean +): TestSubtree { + const query = new TestQueryMultiFile(suite, []); + return { + readableRelativeName: suite + kBigSeparator, + query, + children: new Map(), + collapsible: isCollapsible(query), + }; +} + +function addSubtreeForDirPath( + tree: TestSubtree, + file: string[], + isCollapsible: (sq: TestQuery) => boolean +): TestSubtree { + 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, + file: string[], + isCollapsible: (sq: TestQuery) => boolean +): TestSubtree { + // 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, + test: readonly string[], + testCreationStack: Error, + isCollapsible: (sq: TestQuery) => boolean +): TestSubtree { + 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, + 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( + key: string, + parent: TestSubtree, + createSubtree: () => Omit, 'children'> +): TestSubtree { + let v: TestSubtree; + 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; + } 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, + }; + + // 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]); + } +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/util.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/util.ts new file mode 100644 index 0000000000..37a5db3568 --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/util.ts @@ -0,0 +1,10 @@ +/** + * Error without a stack, which can be used to fatally exit from `tool/` scripts with a + * user-friendly message (and no confusing stack). + */ +export class StacklessError extends Error { + constructor(message: string) { + super(message); + this.stack = undefined; + } +} diff --git a/dom/webgpu/tests/cts/checkout/src/common/internal/version.ts b/dom/webgpu/tests/cts/checkout/src/common/internal/version.ts new file mode 100644 index 0000000000..53cc97482e --- /dev/null +++ b/dom/webgpu/tests/cts/checkout/src/common/internal/version.ts @@ -0,0 +1 @@ +export const version = 'unknown'; -- cgit v1.2.3