🔄

DOMDOMタイムス#18: ノードを並び替えよう(shadow DOMもiframeも突き抜けて！)

2024/05/12に公開

JavaScript

ブラウザ

DOM

tech

久しぶりのDOMDOMタイムス👀
書くたびに久しぶりって言っている気がします！

compareDocumentPositionでノードを並び替えよう！！……ん？？？？

突然ですが、複数のノードをDOMツリーの順で並び替えたいですね！？
(「DOMツリーの順」とは、DOMツリーをpre-orderかつdepth-firstでtraverseする、ただしshadow rootもiframeも見つけ次第ディグっていく、というときの順です👶)

さて、NodeインターフェースにはcompareDocumentPositionというものがあります。
これは2つのノード、つまりthisにあたるノードと引数として与えられたノードの位置関係を取得するためのAPIですね。

MDNの例を一言一句引用してみるよ👶

const head = document.head;
const body = document.body;

if (head.compareDocumentPosition(body) & Node.DOCUMENT_POSITION_FOLLOWING) {
  console.log("正しい形式の文書です");
} else {
  console.error("<head> が <body> の前にありません");
}

結果がビットマスクで返ってくるのが玄人感あってすこです👼ﾗﾌﾞﾘ～
なお、このAPIの詳細はMDNやuhyoさんの解説がとても参考になります。

これを使えば、ノードをDOMの順に並び替えることができますね！

function sortByTreeOrder(nodes) {
    return nodes.slice().sort((a, b) => {
        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
        }
    })
}

……うん、まあ、とは言えDOMのヤバさを知っているわたしたちからすれば、たぶんこれはうまくいかないんだろうなと思うわけです。

まあ実際、これだとうまくいかないんですよね😭

compareDocumentPositionの限界

要するに、別のツリーにいるとアウトです。

iframeおよびshadow DOMは自身を起点に新しいツリーを作れますよね。
そしてcompareDocumentPositionは異なるツリーに属するノードの位置関係までは面倒を見てくれません！

If node1 or node2 is null, or node1’s root is not node2’s root, then return the result of adding DOCUMENT_POSITION_DISCONNECTED, DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC, and either DOCUMENT_POSITION_PRECEDING or DOCUMENT_POSITION_FOLLOWING, with the constraint that this is to be consistent, together.
https://dom.spec.whatwg.org/#dom-node-comparedocumentposition

残念ですねえ。

できらあ！！！！

はい、ここまでは有名な話です。今回は異なるツリーのnodeが混ざった配列でもちゃんと並べ替えられるsortを作ってみました！

要するに共通のrootを見つけて、そのrootが構成するツリーに属するお互いのrootを比較します。

そこまでしっかりテスト書いていないので使うときは自己責任でという感じですが、参考になる気がするのでgistのURLと一緒に置いておきますね！👶
(バグってたら教えてほしいです！笑)

/**
 * 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
 * (If you want the typed version, plz check out the TS version.)
 */
function sortNodesByTreeOrder(nodes) {
  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, b) {
  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, b) {
  // 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 aRootInCommonTree = aIndex > 0 ? getParentOfRoot(aRoots[aIndex - 1]) : a
  const bRootInCommonTree = bIndex > 0 ? getParentOfRoot(bRoots[bIndex - 1]) : b

  return compNodesInSameTree(aRootInCommonTree, bRootInCommonTree)
}

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
}

// The type of `root` is assumed to be `Document` or `ShadowRoot`
const getParentOfRoot = (root) => {
  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) {
  return node.nodeType === Node.DOCUMENT_NODE
}

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

rootをたどっていくのは例のごとく大変なのですが、気合でなんとかしていますね(collectRoots)。

なお、共通祖先rootを見つけるとき、一方のrootさえ集めきれば他方までをも集めきる必要はおそらくありません。ただ、めんどくさかったのでもういいやと思いました👶ﾕﾙｼﾃ~!

おわりに

実際に使ってみてあまりバグっている感じはしなかったのですが、バグっていたら教えてね！！！
ではでは👋

GitHubで編集を提案