Build your own React - Reconciliation

이 포스팅은 AUSG 5기 Frontend Deep Dive 스터디에서 Build your own React 포스팅을 읽고 학습한 내용을 기록한 것입니다. 원문 내용에 더해 React 동작 원리를 이해하는데 도움이 되는 내용이 포함되어 있습니다. 글의 내용과 관련한 피드백은 언제나 환영합니다.

이전에 작성한 Build your own React - React는 어떻게 JSX를 활용하나?와 Build your own React - Concurrent Rendering과 Fiber 포스팅에서 JSX가 DOM element로 바뀌는 과정과 Fiber 자료구조를 활용하여 렌더링 작업을 어떻게 작은 단위로 나누어 처리하는지 알아보았다. 지금까지는 DOM을 새롭게 생성하는 과정에 대해서만 다루었는데, 이번 포스팅에서는 React가 DOM의 변경사항을 처리하는 재조정(Reconciliation) 알고리즘에 대해 알아보자.

Overview

React는 DOM의 변경사항이 생기면 전체 트리를 다시 만들지 않고 변경이 생긴 부분만 업데이트 한다. 이는 어떻게 이뤄지는 것일까? React 공식 문서에 의하면 아무리 최신 트리 변환 알고리즘을 활용하더라도 최대 O(n³)의 복잡도를 가진다. 즉 1000개의 엘리먼트를 그리기 위해 10억 번의 비교 연산을 수행해야 하는 것이다.

이러한 복잡도를 낮추기 위해 React는 약간의 휴리스틱 알고리즘을 이용하여 O(n) 복잡도의 알고리즘을 구현한다. 휴리스틱 알고리즘의 핵심은 다음과 같다.

서로 다른 타입의 두 엘리먼트는 서로 다른 트리를 만들어낸다.
key prop을 통해 여러 렌더링 사이에서 어떤 자식 엘리먼트가 변경되지 않아야 할지 표시해 줄 수 있다.

지금부터 위 휴리스틱 알고리즘에 기반하여 reconciliation 과정이 어떻게 동작하는지 알아보자.

Reconciliation Algorithm

1. 서로 다른 타입의 두 엘리먼트는 서로 다른 트리를 만들어낸다

만약 어떤 DOM 노드의 타입이 바뀌게 된다면, React는 해당 엘리먼트의 서브 트리를 버리고 완전히 새로운 서브트리를 구축한다. 버려질 트리에 포함된 컴포넌트들은 componentWillUnmount() 라이프 사이클 메서드를 실행하고, 새로운 트리에 포함된 컴포넌트들은 UNSAFE_componentWillMount(), componentDidMount()를 이어서 실행한다. 이전 트리와 연관된 모든 state는 사라진다.

예를 들어 다음과 같이 컴포넌트 트리에 변화가 생긴다고 생각해보자.

// before
<div>
  <Counter />
</div>

// after
<span>
  <Counter />
</span>

위 <Counter /> 컴포넌트는 언마운트 되고 다시 마운트된다.

그런데 위와 다르게 만약 element의 타입이 같다면, 변경된 속성만 갱신한다. 또 같은 타입의 컴포넌트 element의 경우 인스턴스는 동일하게 유지되어 state가 유지된다. 컴포넌트의 props가 갱신되면 UNSAFE_componentWillReceiveProps(), UNSAFE_componentWillUpdate(), 그리고 componentDidUpdate() 를 이어서 호출한다.

2. key prop

React는 루트 element를 시작으로 자식에 대해 reconciliation을 재귀적으로 처리하는데, 기본적으로 이전 트리와 새로 생성될 트리를 순회하면서 변경 사항을 처리한다. 예를 들어 다음과 같은 트리를 생각해보자.

// before
<ul>
  <li>하나</li>
  <li>둘</li>
</ul>

// after
<ul>
  <li>하나</li>
  <li>둘</li>
  <li>셋</li>
</ul>

<ul> 태그의 자식으로 <li> 태그를 기존 자식들 맨 끝에 추가했다. 이 경우 React는 새로 생성된 element를 DOM 노드로 잘 생성한다. 그런데 다음의 경우를 보자.

// before
<ul>
  <li>하나</li>
  <li>둘</li>
</ul>

// after
<ul>
  <li>셋</li>
  <li>하나</li>
  <li>둘</li>
</ul>

이 경우 멍청한 알고리즘 이라면 자식 태그를 모두 새롭게 변경할 수 있다. React는 key prop로 이러한 문제를 해결한다. React는 자식 element들이 key를 가지고 있다면 key를 통해 기존 트리와 이후 트리의 자식들이 일치하는지 확인한다.

<ul>
  <li key={1}>하나</li>
  <li key={2}>둘</li>
</ul>

// after
<ul>
  <li key={3}>셋</li>
  <li key={1}>하나</li>
  <li key={2}>둘</li>
</ul>

이렇게 하면 React는 key 가 3인 element만 추가된 것을 알 수 있다. 몇 가지 주의할 사항은 key는 형제 사이에서 unique 해야하고, 배열의 index를 key 로 사용할 경우 재배열 되면 안된다는 것이다.

지금까지 reconciliation이 어떻게 동작하는지 알아보았으니, 이제 직접 구현해보도록 하자.

Step VI: Reconciliation

먼저 이전 트리와 현재 트리를 비교할 수 있어야 하기 때문에, 'DOM tree에 커밋된 바로 직전 트리'를 가리키는 currentRoot 라는 변수를 만든다. 그리고 commit이 된 후 wipRoot 를 currentRoot 에 저장한다.

또 fiber 자료구조에 alternate 필드를 추가하여, 각 fiber가 commit 된 fiber tree의 어떤 fiber와 대응되는지 알 수 있도록 하자.

let currentRoot = null

function commitRoot() {
  commitWork(wipRoot.child)
  // commit 된 root fiber를 currentRoot에 저장
  currentRoot = wipRoot
  wipRoot = null
}

function render(element, container) {
  wipRoot = {
    dom: container,
    props: {
      children: [element],
    },
    // root fiber의 alternate 는 바로 직전에 commit 된 currentRoot 다
    alternate: currentRoot,
  }
  nextUnitOfWork = wipRoot
}

그리고 performUnitOfWork() 함수 안에서 자식 elements에 대한 fiber를 생성하는 로직을 reconcileChildren() 함수 안으로 이동하자.

function performUnitOfWork(fiber) {
  // 1. create dom for fiber...

  const childElements = fiber.props.children
  reconcileChildren(fiber, childElements)

  // 3. select next unit of work...
}

function reconcileChildren(wipFiber, childElements) {
  // TODO: reconcile child elements
}

reconcileChildren() 함수는 이번에 렌더링 할 element(element)와 이에 대응되는 직전에 commit 된 fiber(oldFiber)를 비교하여 변경사항이 생겼다면 이를 반영하여 fiber를 생성하는 기능을 담당한다.

// 삭제할 fiber를 담는 배열
let deletions = null

function render(element, container) {
  // ...
  deletions = []
}

function reconcileChildren(wipFiber, childElements) {
  let index = 0;
  let oldFiber = wipFiber.alternate?.child;
  let prevSibling = null;

  while (oldFiber || index < childElements.length) {
    const element = childElements[index];
    let newFiber = null;

    const sameType = oldFiber?.type === element.type;

    // 1. oldFiber와 element가 같은 타입이라면 DOM 노드를 keep 하고 props 만 업데이트 한다
    if (sameType) {
      newFiber = {
        type: oldFiber.type,
        props: element.props,
        dom: oldFiber.dom,
        parent: wipFiber,
        alternate: oldFiber,
        // effectTag 를 바탕으로 commit phase에서 DOM 노드를
        // 생성("PLACEMENT")/수정("UPDATE")/삭제("DELETION") 한다.
        effectTag: "UPDATE",
      };
    }

    // 2. 타입이 다르면서 element 가 존재하면 새로 DOM 노드를 생성해야 한다
    if (element && !sameType) {
      newFiber = {
        type: element.type,
        props: element.props,
        dom: null,
        parent: wipFiber,
        alternate: null,
        effectTag: "PLACEMENT",
      };
    }

    // 3. 타입이 다르면서 oldFiber가 존재한다면 해당 DOM 노드를 지워줘야 한다.
    if (oldFiber && !sameType) {
      oldFiber.effectTag = "DELETION";
      // oldFiber는 currentRoot에 포함되어 있고, commit phase는 wipRoot 에만 관심이 있기 때문에
      // 삭제할 fiber를 담는 deletions 배열에 추가하고 commit phase에서 삭제해준다
      deletions.push(oldFiber);
    }

    if (oldFiber) {
      oldFiber = oldFiber.sibling;
    }

    if (index === 0) {
      wipFiber.child = newFiber!;
    } else {
      prevSibling!.sibling = newFiber!;
    }

    prevSibling = newFiber;
    index++;
  }
}

Notes: React는 여기서 key prop 도 활용하지만, 단순함을 위해 여기서는 생략한다.

이렇게 해서 reconciliation 기능을 하는 함수를 만들었다. 변경 사항을 바탕으로 fiber를 생성하였기 때문에 이제 commit phase에서 이러한 fiber를 바탕으로 DOM 노드를 생성/수정/삭제해주면 된다.

Commit Phase

먼저 deletions 배열에 담긴 fiber도 commit 할때 처리해준다.

function commitRoot() {
  deletions.forEach(commitWork)

  commitWork(wipRoot.child)
  currentRoot = wipRoot
  wipRoot = null
}

다음으로 commitWork() 함수에서 fiber를 effectTag에 따라 처리해준다. PLACEMENT, DELETION 태그는 간단히 append, remove 해주면 되지만 update는 좀 더 복잡한 연산이 필요하기 때문에 updateDom() 이란 별도의 함수로 분리한다.

function commitWork(fiber) {
  if (!fiber) {
    return
  }
  const domParent = fiber.parent.dom
  if (fiber.effectTag === 'PLACEMENT') {
    domParent.appendChild(fiber.dom)
  }
  if (fiber.effectTag === 'DELETION') {
    domParent.removeChild(fiber.dom)
  }
  if (fiber.effectTag === 'UPDATE') {
    updateDom(fiber.dom, fiber.alternate.props, fiber.props)
  }

  commitWork(fiber.child)
  commitWork(fiber.sibling)
}

function updateDom(dom, prevProps, nextProps) {
  // TODO: update dom node
}

updateDom() 함수 안에서는 이전 fiber와 현재 fiber를 비교하여 제거되거나 변경된 props, event listener를 DOM 노드에서 삭제하고, 새로운 props 와 event listeners를 추가한다.

function updateDom(dom, prevProps, nextProps) {
  const isEvent = (key) => key.startsWith('on')
  const isProperty = (key) => key !== 'children' && !isEvent(key)
  const isGone = (prev: typeof prevProps, next: typeof nextProps) => (key) => !(key in next)
  const isNew = (prev: typeof prevProps, next: typeof nextProps) => (key) => prev[key] !== next[key]

  // Remove old or changed event listeners
  Object.keys(prevProps)
    .filter(isEvent)
    .filter((key) => !(key in nextProps) || isNew(prevProps, nextProps)(key))
    .forEach((name) => {
      const eventName = name.toLowerCase().substr(2)
      dom.removeEventListener(eventName, prevProps[name])
    })

  // Remove old properties
  Object.keys(prevProps)
    .filter(isProperty)
    .filter(isGone(prevProps, nextProps))
    .forEach((name) => {
      dom[name] = ''
    })

  // Set new or changed properties
  Object.keys(nextProps)
    .filter(isProperty)
    .filter(isNew(prevProps, nextProps))
    .forEach((name) => {
      dom[name] = nextProps[name]
    })

  // Add event listeners
  Object.keys(nextProps)
    .filter(isEvent)
    .filter(isNew(prevProps, nextProps))
    .forEach((name) => {
      const eventName = name.toLocaleLowerCase().substr(2)
      dom.addEventListener(eventName, nextProps[name])
    })
}

마지막으로 맨 처음 DOM 을 생성할때도 props, event listener를 추가해주도록 createDom() 함수에서도 updateDom()을 호출해준다. 기존에 props 를 DOM 노드에 추가하던 로직은 제거하자.

function createDom(fiber) {
  const dom =
    fiber.type === "TEXT_ELEMENT"
      ? document.createTextNode("")
      : document.createElement(fiber.type!);

  updateDom(dom, { children: [] }, fiber.props);

  return dom;
}

여기까지 하면 reconciliation 구현이 완료된다. 동작하는 예제는 codesandbox에서 확인할 수 있고 소스코드는 Github 레포지토리에서 확인할 수 있다.

input value가 변경되면 rerender 되어 reconciliation 동작을 확인할 수 있다.