/* global dom, VirtualNode */ // split the page cells to group elements by the position const gridSize = 200; // arbitrary size, increase to reduce memory use (less cells) but increase time (more nodes per grid to check collision) /** * Determine if node produces a stacking context. * References: * https://developer.mozilla.org/en-US/docs/Web/CSS/CSS_Positioning/Understanding_z_index/The_stacking_context * https://github.com/gwwar/z-context/blob/master/devtools/index.js * @param {VirtualNode} vNode * @return {Boolean} */ function isStackingContext(vNode, parentVNode) { const position = vNode.getComputedStylePropertyValue('position'); const zIndex = vNode.getComputedStylePropertyValue('z-index'); // the root element (HTML) is skipped since we always start with a // stacking order of [0] // position: fixed or sticky if (position === 'fixed' || position === 'sticky') { return true; } // positioned (absolutely or relatively) with a z-index value other than "auto", if (zIndex !== 'auto' && position !== 'static') { return true; } // elements with an opacity value less than 1. if (vNode.getComputedStylePropertyValue('opacity') !== '1') { return true; } // elements with a transform value other than "none" const transform = vNode.getComputedStylePropertyValue('-webkit-transform') || vNode.getComputedStylePropertyValue('-ms-transform') || vNode.getComputedStylePropertyValue('transform') || 'none'; if (transform !== 'none') { return true; } // elements with a mix-blend-mode value other than "normal" const mixBlendMode = vNode.getComputedStylePropertyValue('mix-blend-mode'); if (mixBlendMode && mixBlendMode !== 'normal') { return true; } // elements with a filter value other than "none" const filter = vNode.getComputedStylePropertyValue('filter'); if (filter && filter !== 'none') { return true; } // elements with a perspective value other than "none" const perspective = vNode.getComputedStylePropertyValue('perspective'); if (perspective && perspective !== 'none') { return true; } // element with a clip-path value other than "none" const clipPath = vNode.getComputedStylePropertyValue('clip-path'); if (clipPath && clipPath !== 'none') { return true; } // element with a mask value other than "none" const mask = vNode.getComputedStylePropertyValue('-webkit-mask') || vNode.getComputedStylePropertyValue('mask') || 'none'; if (mask !== 'none') { return true; } // element with a mask-image value other than "none" const maskImage = vNode.getComputedStylePropertyValue('-webkit-mask-image') || vNode.getComputedStylePropertyValue('mask-image') || 'none'; if (maskImage !== 'none') { return true; } // element with a mask-border value other than "none" const maskBorder = vNode.getComputedStylePropertyValue('-webkit-mask-border') || vNode.getComputedStylePropertyValue('mask-border') || 'none'; if (maskBorder !== 'none') { return true; } // elements with isolation set to "isolate" if (vNode.getComputedStylePropertyValue('isolation') === 'isolate') { return true; } // transform or opacity in will-change even if you don't specify values for these attributes directly const willChange = vNode.getComputedStylePropertyValue('will-change'); if (willChange === 'transform' || willChange === 'opacity') { return true; } // elements with -webkit-overflow-scrolling set to "touch" if ( vNode.getComputedStylePropertyValue('-webkit-overflow-scrolling') === 'touch' ) { return true; } // element with a contain value of "layout" or "paint" or a composite value // that includes either of them (i.e. contain: strict, contain: content). const contain = vNode.getComputedStylePropertyValue('contain'); if (['layout', 'paint', 'strict', 'content'].includes(contain)) { return true; } // a flex item or gird item with a z-index value other than "auto", that is the parent element display: flex|inline-flex|grid|inline-grid, if (zIndex !== 'auto' && parentVNode) { const parentDsiplay = parentVNode.getComputedStylePropertyValue('display'); if ( [ 'flex', 'inline-flex', 'inline flex', 'grid', 'inline-grid', 'inline grid' ].includes(parentDsiplay) ) { return true; } } return false; } /** * Check if a node or one of it's parents is floated. * Floating position should be inherited from the parent tree * @see https://github.com/dequelabs/axe-core/issues/2222 */ function isFloated(vNode) { if (!vNode) { return false; } if (vNode._isFloated !== undefined) { return vNode._isFloated; } const floatStyle = vNode.getComputedStylePropertyValue('float'); if (floatStyle !== 'none') { vNode._isFloated = true; return true; } const floated = isFloated(vNode.parent); vNode._isFloated = floated; return floated; } /** * Return the index order of how to position this element. return nodes in non-positioned, floating, positioned order * References: * https://developer.mozilla.org/en-US/docs/Web/CSS/CSS_Positioning/Understanding_z_index/Stacking_without_z-index * https://developer.mozilla.org/en-US/docs/Web/CSS/CSS_Positioning/Understanding_z_index/Stacking_and_float * https://drafts.csswg.org/css2/visuren.html#layers * @param {VirtualNode} vNode * @return {Number} */ function getPositionOrder(vNode) { if (vNode.getComputedStylePropertyValue('position') === 'static') { // 5. the in-flow, inline-level, non-positioned descendants, including inline tables and inline blocks. if ( vNode.getComputedStylePropertyValue('display').indexOf('inline') !== -1 ) { return 2; } // 4. the non-positioned floats. if (isFloated(vNode)) { return 1; } // 3. the in-flow, non-inline-level, non-positioned descendants. return 0; } // 6. the child stacking contexts with stack level 0 and the positioned descendants with stack level 0. return 3; } /** * Visually sort nodes based on their stack order * References: * https://drafts.csswg.org/css2/visuren.html#layers * @param {VirtualNode} * @param {VirtualNode} */ function visuallySort(a, b) { /*eslint no-bitwise: 0 */ for (let i = 0; i < a._stackingOrder.length; i++) { if (typeof b._stackingOrder[i] === 'undefined') { return -1; } // 7. the child stacking contexts with positive stack levels (least positive first). if (b._stackingOrder[i] > a._stackingOrder[i]) { return 1; } // 2. the child stacking contexts with negative stack levels (most negative first). if (b._stackingOrder[i] < a._stackingOrder[i]) { return -1; } } // nodes are the same stacking order let aNode = a.actualNode; let bNode = b.actualNode; // elements don't correctly calculate document position when comparing // across shadow boundaries, so we need to compare the position of a // shared host instead // elements have different hosts if (aNode.getRootNode && aNode.getRootNode() !== bNode.getRootNode()) { // keep track of all parent hosts and find the one both nodes share const boundaries = []; while (aNode) { boundaries.push({ root: aNode.getRootNode(), node: aNode }); aNode = aNode.getRootNode().host; } while ( bNode && !boundaries.find(boundary => boundary.root === bNode.getRootNode()) ) { bNode = bNode.getRootNode().host; } // bNode is a node that shares a host with some part of the a parent // shadow tree, find the aNode that shares the same host as bNode aNode = boundaries.find(boundary => boundary.root === bNode.getRootNode()) .node; // sort child of shadow to it's host node by finding which element is // the child of the host and sorting it before the host if (aNode === bNode) { return a.actualNode.getRootNode() !== aNode.getRootNode() ? -1 : 1; } } const { DOCUMENT_POSITION_FOLLOWING, DOCUMENT_POSITION_CONTAINS, DOCUMENT_POSITION_CONTAINED_BY } = window.Node; const docPosition = aNode.compareDocumentPosition(bNode); const DOMOrder = docPosition & DOCUMENT_POSITION_FOLLOWING ? 1 : -1; const isDescendant = docPosition & DOCUMENT_POSITION_CONTAINS || docPosition & DOCUMENT_POSITION_CONTAINED_BY; const aPosition = getPositionOrder(a); const bPosition = getPositionOrder(b); // a child of a positioned element should also be on top of the parent if (aPosition === bPosition || isDescendant) { return DOMOrder; } return bPosition - aPosition; } /** * Determine the stacking order of an element. The stacking order is an array of * zIndex values for each stacking context parent. * @param {VirtualNode} * @return {Number[]} */ function getStackingOrder(vNode, parentVNode) { const stackingOrder = parentVNode._stackingOrder.slice(); const zIndex = vNode.getComputedStylePropertyValue('z-index'); if (zIndex !== 'auto') { stackingOrder[stackingOrder.length - 1] = parseInt(zIndex); } if (isStackingContext(vNode, parentVNode)) { stackingOrder.push(0); } return stackingOrder; } /** * Return the parent node that is a scroll region. * @param {VirtualNode} * @return {VirtualNode|null} */ function findScrollRegionParent(vNode, parentVNode) { let scrollRegionParent = null; let checkedNodes = [vNode]; while (parentVNode) { if (parentVNode._scrollRegionParent) { scrollRegionParent = parentVNode._scrollRegionParent; break; } if (axe.utils.getScroll(parentVNode.actualNode)) { scrollRegionParent = parentVNode; break; } checkedNodes.push(parentVNode); parentVNode = axe.utils.getNodeFromTree( parentVNode.actualNode.parentElement || parentVNode.actualNode.parentNode ); } // cache result of parent scroll region so we don't have to look up the entire // tree again for a child node checkedNodes.forEach( vNode => (vNode._scrollRegionParent = scrollRegionParent) ); return scrollRegionParent; } /** * Add a node to every cell of the grid it intersects with. * @param {Grid} * @param {VirtualNode} */ function addNodeToGrid(grid, vNode) { // save a reference to where this element is in the grid so we // can find it even if it's in a subgrid vNode._grid = grid; vNode.clientRects.forEach(rect => { const x = rect.left; const y = rect.top; // "| 0" is a faster way to do Math.floor // @see https://jsperf.com/math-floor-vs-math-round-vs-parseint/152 const startRow = (y / gridSize) | 0; const startCol = (x / gridSize) | 0; const endRow = ((y + rect.height) / gridSize) | 0; const endCol = ((x + rect.width) / gridSize) | 0; for (let row = startRow; row <= endRow; row++) { grid.cells[row] = grid.cells[row] || []; for (let col = startCol; col <= endCol; col++) { grid.cells[row][col] = grid.cells[row][col] || []; if (!grid.cells[row][col].includes(vNode)) { grid.cells[row][col].push(vNode); } } } }); } /** * Setup the 2d grid and add every element to it, even elements not * included in the flat tree */ function createGrid( root = document.body, rootGrid = { container: null, cells: [] }, parentVNode = null ) { // by not starting at the htmlElement we don't have to pass a custom // filter function into the treeWalker to filter out head elements, // which would be called for every node if (!parentVNode) { let vNode = axe.utils.getNodeFromTree(document.documentElement); if (!vNode) { vNode = new VirtualNode(document.documentElement); } vNode._stackingOrder = [0]; addNodeToGrid(rootGrid, vNode); if (axe.utils.getScroll(vNode.actualNode)) { const subGrid = { container: vNode, cells: [] }; vNode._subGrid = subGrid; } } // IE11 requires the first 3 parameters // @see https://developer.mozilla.org/en-US/docs/Web/API/Document/createTreeWalker const treeWalker = document.createTreeWalker( root, window.NodeFilter.SHOW_ELEMENT, null, false ); let node = parentVNode ? treeWalker.nextNode() : treeWalker.currentNode; while (node) { let vNode = axe.utils.getNodeFromTree(node); // an svg in IE11 does not have a parentElement but instead has a // parentNode. but parentNode could be a shadow root so we need to // verity it's in the tree first if (node.parentElement) { parentVNode = axe.utils.getNodeFromTree(node.parentElement); } else if (node.parentNode && axe.utils.getNodeFromTree(node.parentNode)) { parentVNode = axe.utils.getNodeFromTree(node.parentNode); } if (!vNode) { vNode = new VirtualNode(node, parentVNode); } vNode._stackingOrder = getStackingOrder(vNode, parentVNode); const scrollRegionParent = findScrollRegionParent(vNode, parentVNode); const grid = scrollRegionParent ? scrollRegionParent._subGrid : rootGrid; if (axe.utils.getScroll(vNode.actualNode)) { const subGrid = { container: vNode, cells: [] }; vNode._subGrid = subGrid; } // filter out any elements with 0 width or height // (we don't do this before so we can calculate stacking context // of parents with 0 width/height) const rect = vNode.boundingClientRect; if (rect.width !== 0 && rect.height !== 0 && dom.isVisible(node)) { addNodeToGrid(grid, vNode); } // add shadow root elements to the grid if (axe.utils.isShadowRoot(node)) { createGrid(node.shadowRoot, grid, vNode); } node = treeWalker.nextNode(); } } function getRectStack(grid, rect, recursed = false) { // use center point of rect let x = rect.left + rect.width / 2; let y = rect.top + rect.height / 2; // NOTE: there is a very rare edge case in Chrome vs Firefox that can // return different results of `document.elementsFromPoint`. If the center // point of the element is <1px outside of another elements bounding rect, // Chrome appears to round the number up and return the element while Firefox // keeps the number as is and won't return the element. In this case, we // went with pixel perfect collision rather than rounding const row = (y / gridSize) | 0; const col = (x / gridSize) | 0; let stack = grid.cells[row][col].filter(gridCellNode => { return gridCellNode.clientRects.find(clientRect => { let rectX = clientRect.left; let rectY = clientRect.top; // perform an AABB (axis-aligned bounding box) collision check for the // point inside the rect return ( x <= rectX + clientRect.width && x >= rectX && y <= rectY + clientRect.height && y >= rectY ); }); }); const gridContainer = grid.container; if (gridContainer) { stack = getRectStack( gridContainer._grid, gridContainer.boundingClientRect, true ).concat(stack); } if (!recursed) { stack = stack .sort(visuallySort) .map(vNode => vNode.actualNode) // always make sure html is the last element .concat(document.documentElement) // remove duplicates caused by adding client rects of the same node .filter((node, index, array) => array.indexOf(node) === index); } return stack; } /** * Return all elements that are at the center bounding rect of the passed in node. * @method getElementStack * @memberof axe.commons.dom * @param {Node} node * @return {Node[]} */ dom.getElementStack = function(node) { if (!axe._cache.get('gridCreated')) { createGrid(); axe._cache.set('gridCreated', true); } const vNode = axe.utils.getNodeFromTree(node); const grid = vNode._grid; if (!grid) { return []; } return getRectStack(grid, vNode.boundingClientRect); }; /** * Return all elements that are at the center of each text client rect of the passed in node. * @method getTextElementStack * @memberof axe.commons.dom * @param {Node} node * @return {Array} */ dom.getTextElementStack = function(node) { if (!axe._cache.get('gridCreated')) { createGrid(); axe._cache.set('gridCreated', true); } const vNode = axe.utils.getNodeFromTree(node); const grid = vNode._grid; if (!grid) { return []; } // for code blocks that use syntax highlighting, you can get a ton of client // rects (See https://github.com/dequelabs/axe-core/issues/1985). they use // a mixture of text nodes and other nodes (which will contain their own text // nodes), but all we care about is checking the direct text nodes as the // other nodes will have their own client rects checked. doing this speeds up // color contrast significantly for large syntax highlighted code blocks const clientRects = []; Array.from(node.childNodes).forEach(elm => { if ( elm.nodeType === 3 && axe.commons.text.sanitize(elm.textContent) !== '' ) { const range = document.createRange(); range.selectNodeContents(elm); const rects = range.getClientRects(); for (let i = 0; i < rects.length; i++) { const rect = rects[i]; // filter out 0 width and height rects (newline characters) // ie11 has newline characters return 0.00998, so we'll say if the // line is < 1 it shouldn't be counted if (rect.width >= 1 && rect.height >= 1) { clientRects.push(rect); } } } }); return clientRects.map(rect => { return getRectStack(grid, rect); }); };