sort nodes in shadow-and-iframe-including tree order

sortNodesByTreeOrder.ts

type DocumentOrElement = Document | Element

/**
 * It returns NEW array sorted by shadow(-and-iframe)-including tree order.
 * `shadow-including tree order`: https://dom.spec.whatwg.org/#concept-shadow-including-tree-order
 */
function sortNodesByTreeOrder<T extends DocumentOrElement | Element>(
  nodes: T[]
): T[] {
  return nodes.slice().sort((a, b) => {
    if (!a.isConnected && !b.isConnected) {
      return 0
    }
    if (!a.isConnected) {
      return 1
    } else if (!b.isConnected) {
      return -1
    }

    const comparison = a.compareDocumentPosition(b)
    if (!(comparison & Node.DOCUMENT_POSITION_DISCONNECTED)) {
      return compNodesInSameTree(a, b)
    } else {
      return compNodesInDifferentTree(a, b)
    }
  })
}

function compNodesInSameTree(
  a: Document | Element,
  b: Document | Element
): number {
  const comparison = a.compareDocumentPosition(b)
  if (comparison & Node.DOCUMENT_POSITION_FOLLOWING) {
    return -1
  } else if (comparison & Node.DOCUMENT_POSITION_PRECEDING) {
    return 1
  } else {
    return 0
  }
}

// In the case where a and b are in different trees,
// the result of `compareDocumentPosition` is defined as implementation-specific.
// (ref: https://dom.spec.whatwg.org/#dom-node-comparedocumentposition)
// So, it's necessary to find the closest common root of a and b,
// and then compare their order in the common root's tree.
function compNodesInDifferentTree(
  a: Document | Element,
  b: Document | Element
): number {
  // Strictly speaking, you don't have to collect all the roots of b. It's optimizable.
  const aRoots = collectRoots(a)
  const bRoots = collectRoots(b)
  const nearestCommonRoot = aRoots.find((aRoot) => bRoots.includes(aRoot))

  // At least, `document` is their common root.
  if (!nearestCommonRoot) {
    throw new Error('nearestCommonRoot must be defined')
  }

  const aIndex = aRoots.findIndex((node) => node === nearestCommonRoot)
  const bIndex = bRoots.findIndex((node) => node === nearestCommonRoot)
  if (aIndex === 0 && bIndex === 0) {
    throw new Error('a and b must be in different tree')
  }

  const aNodeInCommonTree = aIndex > 0 ? getParentOfRoot(aRoots[aIndex - 1]) : a
  const bNodeInCommonTree = bIndex > 0 ? getParentOfRoot(bRoots[bIndex - 1]) : b

  return compNodesInSameTree(aNodeInCommonTree, bNodeInCommonTree)
}

function collectRoots(a: Document | Element) {
  const collection = []

  let root = a.getRootNode()
  while (root !== document) {
    if (!(isShadowRoot(root) || isDocument(root))) {
      throw new Error(
        'root must be shadow root or document, because a is connected'
      )
    }
    collection.push(root)

    if (isShadowRoot(root)) {
      root = root.host.getRootNode()
    } else {
      if (!root.defaultView?.frameElement) {
        throw new Error('frameElement must be defined, because a is connected')
      }
      root = root.defaultView.frameElement.getRootNode()
    }
  }
  collection.push(root)

  return collection
}

const getParentOfRoot = (root: Document | ShadowRoot) => {
  if (isDocument(root)) {
    const frame = root.defaultView?.frameElement
    if (!frame) {
      throw new Error('frameElement must be defined')
    }
    return frame
  } else {
    return root.host
  }
}

/////

function isDocument(node: Node): node is Document {
  return node.nodeType === Node.DOCUMENT_NODE
}

function isShadowRoot(node: Node): node is ShadowRoot {
  return node.nodeType === Node.DOCUMENT_FRAGMENT_NODE && 'host' in node
}

js: https://gist.github.com/canalun/8688651b0b613d560b56f8ce5397ad56