Use virtualNode as caching space

[WilcoFiers]

Axe-core is increasingly moving away from directly working with the DOM and abstracting things out. Especially with the introduction of shadow DOM, many of the common methods are no longer in use, such as the usual querySelectorAll, most DOM walking (parentNode, children, etc.), getRoot() and quite a bit more.

One of the problems we have with axe-core is that there is no data sharing between check evaluate calls and between matches. Each runs in its own context and can't take any data from other evaluate / matches calls. This means that many things get computed over and over again. Axe-core does very little in terms of caching. When it comes to querying the DOM for the same thing hundreds of times, or computing the background of the same element thousands of times, these things add up.

The solution: We start putting memoization methods onto the virtualNode. For instance, instead of doing: axe.commons.text.accessibleTextVirtual(virtualNode) we would also allow virtualNode.accessibleText() which when called the first time would call accessibleTextVirtual, and would cache the result for any subsequent calls. I think that would save a bunch of time. Here's a list of methods I think we should move onto the virtualNode:

• accessibleText
• getRole
• isFocusable
• matchesSelector
• getRootNode
• getComposedParent
• findUp
• computedStyle
• isVisible
• getForegroundColor
• getBackgroundColor
• hasContent
• getElementCoordinates
• tabbableElements

[WilcoFiers]

In addition to performance benefits, this also decreases our reliance on global methods which is a big bonus. Further more, we could start thinking about constraining matches/evaluate functions from having access to the DOM at all, which could be a big benefit for making sure custom rules can't do anything malicious.

[stephenmathieson]

We had a quick chat about this and I'm of the opinion we may be better off using an existing memoization tool and just wrapping our existing functions.

For example:

const memoize = axe.imports.memoize

axe.utils.isFocusable = memoize(function (node) {
  // is focusable computation here
})

This leaves the "virtual DOM" abstraction alone and requires very little effort to achieve the same performance win.

NOTE - the memoization tool we use should rely on a WeakMap as its cache rather than trying to stringify DOM nodes.

[WilcoFiers]

@stephenmathieson That would mean axe-core keeps all tested nodes in memory pretty much permanently. I don't think that's ideal.

[stephenmathieson]

@WilcoFiers maybe we fork something like https://www.npmjs.com/package/@emotion/weak-memoize and expose the WeakMap's .clear() method then?

We could do something like:

axe.run = () => {
  memoizeThing.clear()

  // normal axe.run() logic
}

[dylanb]

@stephenmathieson whatever solution we choose should clear the cache at the end of the run call, so the pseudo code should read

axe.run = () => {
   // normal axe.run() logic minus the return/resolve
   memoizeThing.clear()
   // normal axe.run() return/resolve
}

[straker]

Let's memoize (with clearing cache)!

[straker]

Do this for #908