TIL: React의 VDOM Diffing 알고리즘

근데 v15임. 사실 React도 아니고 그냥 HTML DOM임.

React를 사용한 지 어느덧 4년. 뉴노멀이라는 Next.js는 아직 제대로 다루지 못했는데, 마침 원티드의 프론트엔드 챌린지가 있어 강의를 듣다, 문득 메타 프레임워크를 직접 만들고 싶다는 생각이 들었다.
취업 준비는 모르겠고 가슴이 시키는 대로 간다!!!!

Virtual DOM이 유용한 것은 diffing 알고리즘 덕분인데, React의 DOM diffing 알고리즘은 다음 과정으로 이루어진다더라.

1. 트리를 순회할 때, 하위 계층(목록)마다 노드 수를 비교한다.
2. 노드 수가 일치한다면, dirty 표시(mark)된 것만 변경 사항을 반영한다. (dirty 표시는 VDOM 생성 시에 이루어진다)
3. 노드 수가 일치하지 않는다면, 몰?루? key로 찾을 수 있는 노드만 재사용하고 나머진 대충 때려 박는다.

즉, 휴리스틱이다. 개발자들이 코드를 작성하는 패턴(경험)을 토대로 추측한 것.

• 노드가 상위, 또는 하위 계층으로 이동하는 경우는 드물다.
• 계층의 노드 수가 그대로이면, 위치 이동 없이 특정 노드만 변경했을 것이다.
• 계층의 노드 수가 변했다면, 아마도 map으로 노드를 나열했을 테니 key를 이용해 최적화하겠다.

근데 글의 출처가 2013년 12월이다. 지금의 React는 어떨까 싶어 GitHub으로 달려갔는데... Fiber 도입 이후로는 코드 상의 흐름이 직관적이지 못해 비교적 쉬운 15 버전의 React를 뜯어 봤다.

어차피 DOM과 DOM을 비교하려는 나에게 Fiber는 굳이 뜯어볼 필요가 없기도 하고. Fiber 아키텍처는 거대하지만, diffing 알고리즘 내에서의 Fiber의 역할은 React만의 무언가(Component, Fragment, Memo, Effect 등)를 처리하기 위함이라. 나중에 v16, v18과 비교할 일이 생긴다면 뜯어보고 글로 쓰는 걸로. (근데 이미 유명한 글이 있다. 이렇게까지는 못 쓸 것 같은데? React 톺아보기)

react/old_major_packages/15/react-dom/dist/react-dom.js at v15.7.0 · facebook/react

The library for web and native user interfaces. Contribute to facebook/react development by creating an account on GitHub.

GitHubfacebook

// https://github.com/facebook/react/blob/v15.7.0/old_major_packages/15/react-dom/dist/react-dom.js

ReactDOMComponent.updateComponent // #1. UpdateElement
  ReactDOMComponent._updateDOMProperties // #2. UpdateAttributes
  ReactDOMComponent._updateDOMChildren // #3. UpdateChildNodes

/* --- */

ReactDOMComponent._updateDOMChildren
  ReactMultiChild.updateChildren
    ReactMultiChild._updateChildren // #5. SortChildNodes
      ReactMultiChild._reconcilerUpdateChildren
        ReactChildReconciler.updateChildren // #4. PatchChildNodes
          ReactReconciler.mountComponent
          ReactReconciler.unmountComponent
          ReactReconciler.receiveComponent
            ReactDOMComponent.updateComponent // Recursive (#1)
      ReactMultiChild.processQueue

ReactDOMComponent._updateDOMChildren
  ReactMultiChild.updateTextContent
    ReactMultiChild.processQueue

ReactDOMComponent._updateDOMChildren
  ReactMultiChild.updateMarkup
    ReactMultiChild.processQueue

/* --- */

ReactMultiChild.processQueue
  ReactComponentBrowserEnvironment.processChildrenUpdates
    ReactDOMIDOperations.dangerouslyProcessChildrenUpdates
      DOMChildrenOperations.processUpdates // (#6. Flush)

React v15의 DOM 업데이트 로직의 함수 실행 흐름이다.
핵심 로직이 포함된 함수에 번호를 매겼는데, 실행 순서보다는 알고리즘의 흐름에 따라 적어두었다.

과거의 렌더링 결과를 OLD, 새로운 렌더링 결과를 NEW로 표현하고,
순수 DOM과 무관한 React의 구현은 key만 포함, 나머진 모두 제외한다.

1. OLD element와 NEW element의 비교로 시작한다. (UpdateElement)
2. OLD element의 attributes를 NEW element의 attributes로 업데이트한다. (UpdateAttributes)
3. OLD element의 child nodes를 NEW element의 child nodes로 업데이트를 시작한다. (UpdateChildNodes)
4. NEW element의 child nodes를 순회하면서 key가 동일한 OLD child element를 찾는다. (PatchChildNodes)
5. 4번 조건의 element를 찾았고 재사용할 수 있다면:
   UpdateElement를 재귀 호출해, 해당 element를 재사용하면서 NEW element에 맞게 업데이트한다.
6. 4번 조건의 element를 찾지 못했거나, 찾았지만 재사용할 수 없다면:
   해당 element를 삭제하고 NEW element를 마지막에 추가한다.
7. 순회가 끝나면, 처리되지 않은 OLD child nodes를 모두 제거한다.
8. NEW child nodes의 순서를 정렬한다. (SortChildNodes)

8번 정렬 과정에서 DOM 조작 비용이 추가되었는데, React는 지금까지의 작업을 큐에 담아두고 Flush에서 처리한다.
DOM을 직접 제어하고 있고 태스크 큐를 따로 관리하지 않는다면, 4–8의 과정을 적절히 합치는 게 좋을 것.

wmf/poc/web-components/src/utils/updateChildNodes.ts at dev · choegyumin/wmf

Web components(custom elements) Meta Framework. Contribute to choegyumin/wmf development by creating an account on GitHub.

GitHubchoegyumin

다른 코드도 적당히 참고하며, 구현하고 나서야 이게 맞나? 하고 뜯어 봤는데... 꽤나 비슷한 것 같기도?

VDOM과 비교하려고 Signal도 잠깐 학습했었는데, 나중에 더 학습하고 글로 다루어봐야겠다.