Analyzing spec algorithms

[tidoust]

Context: algorithms extraction

Reffy now extracts algorithms from specs, see algorithms extracts in Webref. Extraction is far from perfect (a number of limitations are noted as TODO comments in the extraction logic) but the results are still good enough to start analyzing potential problems in algorithms, see study-algorithms.js.

Also see @dontcallmedom's initial algorithms explorer based on the extracts.

Analysis: parallel steps that should call "queue a task"

First thing I analyzed are steps that run in parallel because I always forget the need to queue a task within parallel steps before resolving/rejecting a Promise or firing an event. @jyasskin noted the same problem back in 2022 in whatwg/html#8569. What's new here is that we can now compute that information automatically, giving us more weapons to play whack-a-mole.

The results show that about 50% of the specs (56/113) that define algorithms with "in parallel" steps need fixing:

Specs with steps in parallel that miss a call to "queue a task" (56 specs)

• Accelerated Shape Detection in Images
  • The BarcodeDetector/getSupportedFormats() algorithm has a parallel step that resolves/rejects a promise directly
• Audio Output Devices API
  • The HTMLMediaElement/setSinkId() algorithm has a parallel step that resolves/rejects a promise directly
  • The MediaDevices/selectAudioOutput() algorithm has a parallel step that resolves/rejects a promise directly
• Background Fetch
  • The create record objects algorithm has a parallel step that resolves/rejects a promise directly
  • The get(id) algorithm has a parallel step that resolves/rejects a promise directly
  • The getIds() algorithm has a parallel step that resolves/rejects a promise directly
  • The abort() algorithm has a parallel step that resolves/rejects a promise directly
  • The updateUI(options) algorithm has a parallel step that resolves/rejects a promise directly
• Contact Picker API
  • The getProperties() algorithm has a parallel step that resolves/rejects a promise directly
• Content Index
  • The add(description) algorithm has a parallel step that resolves/rejects a promise directly
  • The delete(id) algorithm has a parallel step that resolves/rejects a promise directly
  • The getAll() algorithm has a parallel step that resolves/rejects a promise directly
• Cookie Store API
  • The CookieStore/get(name) algorithm has a parallel step that resolves/rejects a promise directly
  • The CookieStore/get(options) algorithm has a parallel step that resolves/rejects a promise directly
  • The CookieStore/getAll(name) algorithm has a parallel step that resolves/rejects a promise directly
  • The CookieStore/getAll(options) algorithm has a parallel step that resolves/rejects a promise directly
  • The CookieStore/set(name, value) algorithm has a parallel step that resolves/rejects a promise directly
  • The CookieStore/set(options) algorithm has a parallel step that resolves/rejects a promise directly
  • The CookieStore/delete(name) algorithm has a parallel step that resolves/rejects a promise directly
  • The CookieStore/delete(options) algorithm has a parallel step that resolves/rejects a promise directly
  • The CookieStoreManager/subscribe(subscriptions) algorithm has a parallel step that resolves/rejects a promise directly
  • The CookieStoreManager/getSubscriptions() algorithm has a parallel step that resolves/rejects a promise directly
  • The CookieStoreManager/unsubscribe(subscriptions) algorithm has a parallel step that resolves/rejects a promise directly
• Credential Management Level 1
  • The Request a Credential algorithm has a parallel step that resolves/rejects a promise directly
  • The Create a Credential algorithm has a parallel step that resolves/rejects a promise directly
  • The Prevent Silent Access algorithm has a parallel step that resolves/rejects a promise directly
• CSS Object Model (CSSOM)
  • The CSSStyleSheet/replace(text) algorithm has a parallel step that resolves/rejects a promise directly
• Element Capture
  • The BrowserCaptureMediaStreamTrack/restrictTo() algorithm has a parallel step that resolves/rejects a promise directly
• Encrypted Media Extensions
  • The Navigator/requestMediaKeySystemAccess() algorithm has a parallel step that resolves/rejects a promise directly
  • The MediaKeySystemAccess/createMediaKeys() algorithm has a parallel step that resolves/rejects a promise directly
  • The MediaKeys/setServerCertificate() algorithm has a parallel step that resolves/rejects a promise directly
  • The MediaKeySession/generateRequest() algorithm has a parallel step that resolves/rejects a promise directly
  • The MediaKeySession/load() algorithm has a parallel step that resolves/rejects a promise directly
  • The MediaKeySession/update() algorithm has a parallel step that resolves/rejects a promise directly
  • The HTMLMediaElement/setMediaKeys() algorithm has a parallel step that resolves/rejects a promise directly
• EyeDropper API
  • The EyeDropper/open() algorithm has a parallel step that resolves/rejects a promise directly
• Federated Credential Management API
  • The attempt to disconnect algorithm has a parallel step that resolves/rejects a promise directly
  • The getUserInfo algorithm has a parallel step that resolves/rejects a promise directly
• File System Access
  • The FileSystemHandle/queryPermission(descriptor) algorithm has a parallel step that resolves/rejects a promise directly
  • The FileSystemHandle/requestPermission(descriptor) algorithm has a parallel step that resolves/rejects a promise directly
  • The Window/showOpenFilePicker(options) algorithm has a parallel step that resolves/rejects a promise directly
  • The Window/showSaveFilePicker(options) algorithm has a parallel step that resolves/rejects a promise directly
  • The Window/showDirectoryPicker(options) algorithm has a parallel step that resolves/rejects a promise directly
  • The DataTransferItem/getAsFileSystemHandle() algorithm has a parallel step that resolves/rejects a promise directly
• Fullscreen API Standard
  • The requestFullscreen(options) algorithm has a parallel step that resolves/rejects a promise directly
  • The exit fullscreen algorithm has a parallel step that resolves/rejects a promise directly
• Gamepad
  • The GamepadHapticActuator/reset() algorithm has a parallel step that resolves/rejects a promise directly
• Geolocation Sensor
  • The read algorithm has a parallel step that resolves/rejects a promise directly
• Get Installed Related Apps API
  • The getInstalledRelatedApps() algorithm has a parallel step that resolves/rejects a promise directly
• Handwriting Recognition API
  • The navigator-query-handwriting-recognizer algorithm has a parallel step that resolves/rejects a promise directly
  • The navigator-create-handwriting-recognizer algorithm has a parallel step that resolves/rejects a promise directly
  • The handwriting-drawing-get-prediction algorithm has a parallel step that resolves/rejects a promise directly
• HTML Standard
  • The HTMLImageElement/decode() algorithm has a parallel step that resolves/rejects a promise directly
  • The WindowOrWorkerGlobalScope/createImageBitmap(image, options) algorithm has a parallel step that resolves/rejects a promise directly
• Idle Detection API
  • The IdleDetector/requestPermission() algorithm has a parallel step that resolves/rejects a promise directly
• Indexed Database API 3.0
  • The IDBFactory/databases() algorithm has a parallel step that resolves/rejects a promise directly
• JS Self-Profiling API
  • The algorithm that starts with "Stops the profiler and returns a trace. This method MUST run these steps:" has a parallel step that resolves/rejects a promise directly
• Keyboard Map
  • The keyboard-getlayoutmap algorithm has a parallel step that resolves/rejects a promise directly
• Local Font Access API
  • The Window/queryLocalFonts(options) algorithm has a parallel step that resolves/rejects a promise directly
  • The FontData/blob() algorithm has a parallel step that resolves/rejects a promise directly
• Managed Configuration API
  • The NavigatorManagedData/getManagedConfiguration(keys) algorithm has a parallel step that resolves/rejects a promise directly
• Media Capabilities
  • The algorithm that starts with "The decodingInfo() method method MUST run the following steps:" has a parallel step that resolves/rejects a promise directly
  • The algorithm that starts with "The encodingInfo() method MUST run the following steps:" has a parallel step that resolves/rejects a promise directly
• Media Capture and Streams
  • The MediaDevices/enumerateDevices() algorithm has a parallel step that resolves/rejects a promise directly
  • The MediaDevices/getUserMedia() algorithm has a parallel step that resolves/rejects a promise directly
• Media Session
  • The update capture state algorithm algorithm has a parallel step that resolves/rejects a promise directly
• MediaStream Image Capture
  • The ImageCapture/takePhoto(photoSettings) algorithm has a parallel step that resolves/rejects a promise directly
  • The ImageCapture/getPhotoCapabilities() algorithm has a parallel step that resolves/rejects a promise directly
  • The ImageCapture/getPhotoSettings() algorithm has a parallel step that resolves/rejects a promise directly
  • The ImageCapture/grabFrame() algorithm has a parallel step that resolves/rejects a promise directly
• Payment Handler API
  • The algorithm that starts with "Upon receiving a PaymentRequest by way of PaymentRequest.show() and subsequent user selection of a payment handler, the user agent MUST run the following steps:" has a parallel step that resolves/rejects a promise directly
  • An algorithm has a parallel step that resolves/rejects a promise directly
• Payment Request API
  • The algorithm that starts with "The show(optional detailsPromise) method MUST act as follows:" has a parallel step that resolves/rejects a promise directly
  • The algorithm that starts with "The complete() method MUST act as follows:" has a parallel step that resolves/rejects a promise directly
  • The can make payment algorithm algorithm has a parallel step that resolves/rejects a promise directly
• Picture-in-Picture
  • The algorithm that starts with "The requestPictureInPicture() method, when invoked, MUST return a new promise promise and run the following steps in parallel:" has a parallel step that resolves/rejects a promise directly
  • The algorithm that starts with "The exitPictureInPicture() method, when invoked, MUST return a new promise promise and run the following steps in parallel:" has a parallel step that resolves/rejects a promise directly
• Presentation API
  • The PresentationRequest/start() algorithm has a parallel step that resolves/rejects a promise directly
  • The PresentationRequest/reconnect() algorithm has a parallel step that resolves/rejects a promise directly
  • The PresentationRequest/getAvailability() algorithm has a parallel step that resolves/rejects a promise directly
  • The monitoring incoming presentation connections algorithm has a parallel step that resolves/rejects a promise directly
• Region Capture
  • The BrowserCaptureMediaStreamTrack/cropTo() algorithm has a parallel step that resolves/rejects a promise directly
• Remote Playback API
  • The RemotePlayback/prompt() algorithm has a parallel step that resolves/rejects a promise directly
• Screen Capture
  • The MediaDevices/getDisplayMedia() algorithm has a parallel step that resolves/rejects a promise directly
• Screen Orientation
  • The apply orientation lock algorithm has a parallel step that resolves/rejects a promise directly
• Service Workers Nightly
  • The navigator-service-worker-getRegistration algorithm has a parallel step that resolves/rejects a promise directly
  • The navigation-preload-manager-enable algorithm has a parallel step that resolves/rejects a promise directly
  • The navigation-preload-manager-disable algorithm has a parallel step that resolves/rejects a promise directly
  • The navigation-preload-manager-setheadervalue algorithm has a parallel step that resolves/rejects a promise directly
  • The navigation-preload-manager-getstate algorithm has a parallel step that resolves/rejects a promise directly
  • The service-worker-global-scope-skipwaiting algorithm has a parallel step that resolves/rejects a promise directly
  • The client-postmessage-options algorithm has a parallel step that fires an event directly
  • The clients-get algorithm has a parallel step that resolves/rejects a promise directly
  • The clients-claim algorithm has a parallel step that resolves/rejects a promise directly
  • The cache-match algorithm has a parallel step that resolves/rejects a promise directly
  • The cache-matchall algorithm has a parallel step that resolves/rejects a promise directly
  • The cache-storage-match algorithm has a parallel step that resolves/rejects a promise directly
  • The cache-storage-has algorithm has a parallel step that resolves/rejects a promise directly
  • The cache-storage-open algorithm has a parallel step that resolves/rejects a promise directly
  • The cache-storage-delete algorithm has a parallel step that resolves/rejects a promise directly
  • The cache-storage-keys algorithm has a parallel step that resolves/rejects a promise directly
  • The Handle Fetch algorithm has a parallel step that resolves/rejects a promise directly
• Test Utils Standard
  • The algorithm that starts with "The gc() method must run these steps:" has a parallel step that resolves/rejects a promise directly
• The Capture-Handle Actions Mechanism
  • The MediaStreamTrack/sendCaptureAction() algorithm has a parallel step that resolves/rejects a promise directly
• Viewport Capture
  • The MediaDevices/getViewportMedia() algorithm has a parallel step that resolves/rejects a promise directly
• VirtualKeyboard API
  • The VirtualKeyboard/show() algorithm has a parallel step that fires an event directly
  • The VirtualKeyboard/hide() algorithm has a parallel step that fires an event directly
• Web Background Synchronization
  • The SyncManager/register(tag) algorithm has a parallel step that resolves/rejects a promise directly
  • The SyncManager/getTags() algorithm has a parallel step that resolves/rejects a promise directly
  • The fire a sync event algorithm has a parallel step that fires an event directly
• Web Bluetooth
  • The getDevice invocation algorithm has a parallel step that resolves/rejects a promise directly
  • The requestDevice invocation algorithm has a parallel step that resolves/rejects a promise directly
  • The query Bluetooth cache algorithm has a parallel step that resolves/rejects a promise directly
  • The BluetoothRemoteGATTServer connect algorithm has a parallel step that resolves/rejects a promise directly
  • The BluetoothRemoteGATTService construction algorithm has a parallel step that resolves/rejects a promise directly
  • The BluetoothRemoteGATTCharacteristic constructor algorithm has a parallel step that resolves/rejects a promise directly
  • The BluetoothRemoteGATTCharacteristic readValue() algorithm has a parallel step that resolves/rejects a promise directly
  • The Write Characteristic value algorithm has a parallel step that resolves/rejects a promise directly
  • The BluetoothRemoteGATTCharacteristic startNotifications algorithm has a parallel step that resolves/rejects a promise directly
  • The BluetoothCharacteristicProperties constructor algorithm has a parallel step that resolves/rejects a promise directly
  • The BluetoothRemoteGATTDescriptor constructor algorithm has a parallel step that resolves/rejects a promise directly
  • The BluetoothRemoteGATTDescriptor readValue algorithm has a parallel step that resolves/rejects a promise directly
  • The BluetoothRemoteGATTDescriptor writeValue algorithm has a parallel step that resolves/rejects a promise directly
• Web Bluetooth Scanning
  • The Bluetooth/requestLEScan(options) algorithm has a parallel step that resolves/rejects a promise directly
• Web Cryptography API
  • The SubtleCrypto/encrypt() algorithm has a parallel step that resolves/rejects a promise directly
  • The SubtleCrypto/sign() algorithm has a parallel step that resolves/rejects a promise directly
  • The SubtleCrypto/digest() algorithm has a parallel step that resolves/rejects a promise directly
  • The SubtleCrypto/generateKey() algorithm has a parallel step that resolves/rejects a promise directly
  • The SubtleCrypto/deriveKey() algorithm has a parallel step that resolves/rejects a promise directly
  • The SubtleCrypto/deriveBits() algorithm has a parallel step that resolves/rejects a promise directly
  • The SubtleCrypto/importKey() algorithm has a parallel step that resolves/rejects a promise directly
  • The SubtleCrypto/exportKey() algorithm has a parallel step that resolves/rejects a promise directly
  • The SubtleCrypto/wrapKey() algorithm has a parallel step that resolves/rejects a promise directly
  • The SubtleCrypto/unwrapKey() algorithm has a parallel step that resolves/rejects a promise directly
• Web NFC
  • The NDEFReader/write() algorithm has a parallel step that resolves/rejects a promise directly
  • The NDEFReader/makeReadOnly() algorithm has a parallel step that resolves/rejects a promise directly
  • The clean up the pending scan algorithm has a parallel step that resolves/rejects a promise directly
• Web Periodic Background Synchronization
  • The Process periodic sync registrations algorithm has a parallel step that fires an event directly
• WebCodecs
  • The ImageDecoder/isTypeSupported(type) algorithm has a parallel step that resolves/rejects a promise directly
• WebDriver
  • The algorithm that starts with "The remote end steps, given session, URL variables and parameters are:" has a parallel step that resolves/rejects a promise directly
  • The algorithm that starts with "The remote end steps, given session, URL variables and parameters are:" has a parallel step that resolves/rejects a promise directly
• WebHID API
  • The algorithm that starts with "The forget() method steps are:" has a parallel step that resolves/rejects a promise directly
• WebRTC Encoded Transform
  • The algorithm that starts with "The SFrame transform algorithm, given sframe as a SFrameTransform object and frame, runs these steps:" has a parallel step that resolves/rejects a promise directly
  • The generate key frame algorithm algorithm has a parallel step that resolves/rejects a promise directly
  • The send request key frame algorithm algorithm has a parallel step that resolves/rejects a promise directly
• WebRTC: Real-Time Communication in Browsers
  • The RTCPeerConnection/generateCertificate() algorithm has a parallel step that resolves/rejects a promise directly
  • The RTCRtpSender/replaceTrack() algorithm has a parallel step that resolves/rejects a promise directly
  • The RTCRtpSender/getStats() algorithm has a parallel step that resolves/rejects a promise directly
  • The RTCRtpReceiver/getStats() algorithm has a parallel step that resolves/rejects a promise directly
  • The RTCPeerConnection/getStats() algorithm has a parallel step that resolves/rejects a promise directly
• WebTransport
  • The WebTransport/getStats() algorithm has a parallel step that resolves/rejects a promise directly
  • The WebTransport/createBidirectionalStream(options) algorithm has a parallel step that resolves/rejects a promise directly
  • The WebTransport/createUnidirectionalStream(options) algorithm has a parallel step that resolves/rejects a promise directly
• WebUSB API
  • The algorithm that starts with "The getDevices() method, when invoked, MUST return a new Promise and run the following steps in parallel:" has a parallel step that resolves/rejects a promise directly
  • The request the "usb" permission algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.open() algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.close() algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.forget() algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.selectConfiguration(configurationValue) algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.claimInterface(interfaceNumber) algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.releaseInterface(interfaceNumber) algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.selectAlternateInterface(interfaceNumber, alternateSetting) algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.controlTransferIn(setup, length) algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.controlTransferOut(setup, data) algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.clearHalt(direction, endpointNumber) algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.transferIn(endpointNumber, length) algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.transferOut(endpointNumber, data) algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.isochronousTransferIn(endpointNumber, packetLengths) algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.isochronousTransferOut(endpointNumber, data, packetLengths) algorithm has a parallel step that resolves/rejects a promise directly
  • The USBDevice.reset() algorithm has a parallel step that resolves/rejects a promise directly
• WebXR Device API
  • The session-supported algorithm has a parallel step that resolves/rejects a promise directly
  • The request-reference-space algorithm has a parallel step that resolves/rejects a promise directly

To run the analysis and refresh the above results, retrieve Webref's latest crawl results data locally and run:

npx strudy inspect [pathto]/webref --what algorithms --structure type/spec --sort default/title > res.md

On top of these problems (Edit: both examples have been fixed):

• The example on using AbortController and AbortSignal objects in the DOM spec seems wrong: step 3.2 should queue a task to resolve p with amazingResult (but note step 2.3.2 seems correct, because abort steps run within a global task)
  (Edit: reported in Missing "queue a global task" to resolve Promise in abort example whatwg/dom#1300)
• The parallel queue example in the Parallelism section in HTML seems wrong as well: steps 2.4 in both the "incorrect" and "correct" versions should also queue a task, the former because the step explicitly runs "in parallel" in step 2, the latter because steps enqueued to a parallel queue also run in parallel, I think.
  (Edit: reported in Example in parallelism section needs to "queue a task" to handle the promise whatwg/html#10535)

We could start reporting these problems to spec authors on a semi-automated basis (after review) as we do for broken links. Now, as noted by @jyasskin in whatwg/html#8569, "queue a task" means selecting a task source, which is also something that people get confused about (looking into it, I realize that I raised w3ctag/design-principles#38 on this topic back in 2016), and often choose to ignore.

Given the number of specs that get it wrong, two questions that I'm wondering about:

1. Would it be better to consider less error prone ways to write such steps first?
2. Do these problems materialize in interoperability bugs? Should we rather keep that in the back burner if it does not have practical implications?

Further analyses

Additional analyses that could be done:

• Look into task sources as well. Whether a task source is defined is a bit harder to evaluate automatically because various specs have a blanket "use the foo task source for all tasks in this specification" statement; but the name of the task source is usually wrapped in a <dfn>, which should be easy to detect.
• Report terms in steps that should link to their formal definition (e.g., "in parallel", "queue a task") and that don't.
• Look into phrasing conventions when defining an algorithm and calling an algorithm, to progressively converge on a similar pseudo-language for algorithms. See how to define an algorithm in Infra for the definition part.
• Start tracking algorithm variables, inputs and outputs. That probably requires settling down on stricter conventions first.
• Analyze the list of step operations. In the extraction logic, the list is used to assess that a list item is indeed part of an algorithm. It reveals the many verbs that specs use to tell implementers what needs to be done. Some have formal definitions. The meaning of others is more fuzzy. Ideally, the meaning of all operations would be normatively defined somewhere.

Any other interesting or important analyses that could be worth looking into?

How to write/flag algorithms

More broadly speaking, algorithms are currently written with semi-formal structures. There are opportunities to converge on a more formal structure if that seems useful. Examples:

• Infra describes how to define an algorithm. Specs use other variants here and there, such as "When the foo() method is invoked, run the following steps...", or algorithms sections where the sub-heading's title is the name of the algorithm.
• Specs and spec authoring tools follow different conventions with regards to flagging these algorithms, e.g., with a class="algorithm" attribute. This makes it harder to extract the relevant prose, algorithm name, and actual steps.
• Algorithm steps may be more or less atomic. Sometimes, a single step performs multiple operations (e.g., if/then/else all in one sentence). Related discussions about "inlining" steps in HTML in "in parallel" in algorithm headers can be confusing whatwg/html#10049

On top of us raising issues afterwards, spec authoring tools could perhaps better guide spec authors at the authoring step. Additional classes could also help make algorithms visually more readable, as attempted with flowchart symbols in the algorithms explorer.

In any case, convergence would make it easier to extract the algorithms and run further analyses.

[tidoust]

Status update:

• Strudy was re-written to ease semi-automatic reporting of various types of anomalies.
• This made it possible to file "missing "ueue a task" issues against specifications, which we've now started to do. That may take a bit of time but anomalies reported above should end up being reported.
• I sent a message to spec-prod to initiate a larger discussion about algorithms