트리 자료구조를 중심으로 DOM 탐색 과정 살펴보기
WebKit 의 getElementById 구현부 간략히 살펴보기
추측 및 주관적인 생각이 많이 들어가 있어 잘못된 부분이 있을 수 있습니다.
틀리거나 오해한 부분은 댓글로 알려주시면 감사하겠습니다.
들어가며
🐠 DOM (Document Object Model) 이란 무엇일까요? 🐟
DOM은 브라우저가 전달받은 문서를 해석, 구조화해놓은 결과물입니다. 이 DOM을 기준으로 브라우저는 일련의 과정을 거쳐 실제 화면을 보여줍니다.
우리가 크롬, 사파리같은 브라우저를 통해 특정 URL에 접속했을 때를 상상해봅시다. 브라우저는 그 URL에 해당하는 페이지를 달라고 서버에게 요청하고 서버는 해당 요청에 대한 적절한 응답을 브라우저에게 내려줍니다. 여기서 '적절한 응답'은 당연히 브라우저가 알아들을 수 있는 형태의 문서인데, 보통 HTML, CSS, JS 등으로 이루어져 있습니다.
이러한 형태의 파일 포맷은 우리가 기대하는 예쁜 뷰의 웹페이지와는 거리가 다소 있어서, 브라우저는 이 문서의 내용물들을 인식해 사용자가 볼 수 있도록 잘 바꿔 구성하고 결과적으로 우리는 잘 조립된 구조의 웹페이지를 보게 됩니다. 여기서 브라우저는 응답받은 문서를 보통 트리 구조로 변환하는데 이를 DOM이라고 부릅니다.
웹페이지를 돌아다니다 보면 우리는 이 DOM에 접근할 일이 굉장히 많습니다. 찾고, 수정하고, 삭제합니다. 브라우저 선생님한테 감정 이입을 좀 하자면, 사용자에게 응답받은 문서를 잘 보여주고 싶은 마음에 아래 두 가지를 고려하고 싶었을 것 같았습니다.
1. 문서의 특징을 잘 나타낼 수 있는 자료구조로 바꿔야 하는데..
2. 문서가 변경되었을 때 유연하게 대처할 수 있는 자료구조로 바꿔야 하는데..
이번 포스팅에서는 이러한 DOM을 자료구조에 초점을 맞춰 살펴볼 예정입니다.
DOM이란?
mozilla에 정의되어 있는 DOM
... 문서 객체 모델(The Document Object Model, 이하 DOM)은 HTML, XML 문서의 프로그래밍 interface 이다. DOM은 문서의 구조화된 표현(structured representation)을 제공하며 프로그래밍 언어가 DOM 구조에 접근할 수 있는 방법을 제공하여 그들이 문서 구조, 스타일, 내용 등을 변경할 수 있게 돕는다. DOM 은 nodes와 objects로 문서를 표현한다. 이들은 웹 페이지를 스크립트 또는 프로그래밍 언어들에서 사용될 수 있게 연결시켜주는 역할을 담당한다. 웹 페이지는 일종의 문서(document)다. 이 문서는 웹 브라우저를 통해 그 내용이 해석되어 웹 브라우저 화면에 나타나거나 HTML 소스 자체로 나타나기도 한다. 동일한 문서를 사용하여 이처럼 다른 형태로 나타날 수 있다는 점에 주목할 필요가 있다. DOM 은 동일한 문서를 표현하고, 저장하고, 조작하는 방법을 제공한다. DOM 은 웹 페이지의 객체 지향 표현이며, 자바스크립트와 같은 스크립팅 언어를 이용해 DOM 을 수정할 수 있다. W3C DOM, WHATWG DOM 표준은 대부분의 브라우저에서 DOM 을 구현하는 기준이다. 많은 브라우저들이 표준 규약에서 제공하는 기능 외에도 추가적인 기능들을 제공하기 때문에 사용자가 작성한 문서들이 각기 다른 DOM 이 적용된 다양한 브라우저 환경에서 동작할 수 있다는 사실을 항상 인지하고 있어야 한다. ...
왜 DOM은 트리 구조인가?
DOM은 파싱의 결과물입니다. DOM 트리는 일반적으로 이름처럼 트리 자료구조로 구현되어있다고 알려져 있습니다. HTML 문서의 태그들은 부모와 자식 관계처럼 상위 태그가 하위 태그를 감싸는 형태를 반복하고 있는데 이를 계층관계로 보면 자료를 표현하기가 쉽습니다.
<p>At Mozilla, we're a global community of</p>
<ul>
<li>technologists</li>
<li>thinkers</li>
<li>builders</li>
</ul>
<p>working together…</p>
또한 웹페이지는 사용자와의 상호작용을 계속해서 해야합니다. 사용자가 글을 쓸 수도 있고, 글을 삭제할 수도 있습니다. 혹은 인터랙션이 있는 계속 있는 페이지라면 사용자의 마우스 이벤트에 따라서도 짧은 순간에 구조가 달라질 수도 있습니다.
이 때 어떤 태그의 하위 태그로 새로운 요소가 들어가야하는지, 어떤 요소를 삭제해야하는지가 중요한데 이 연산의 시작은 바로 어떤 노드를 기준으로 연산을 진행할지 찾는 '탐색'입니다. 결국 DOM을 나타내기에는 계층 관계를 나타내면서도 탐색 효율이 좋은 자료구조인 트리가 적합해 보입니다. 트리 자료구조는 자료들을 계층적으로 구조화하기에 용이한 비선형 자료구조이며, 주로 저장된 데이터를 효과적으로 탐색하기에 좋습니다.
DOM tree를 구성하는 네 종류의 노드
DOM 트리를 구성하는 노드는 크게 4종류로 나뉘는데, 각각의 특성은 아래와 같고 아래 링크에서 가져왔습니다.
DOM | PoiemaWeb
브라우저는 웹 문서(HTML, XML, SVG)를 로드한 후, 파싱하여 DOM(문서 객체 모델. Document Object Model)을 생성한다. 파일로 만들어져 있는 웹 문서를 브라우저에 렌더링하기 위해서는 웹 문서를 브라우저
poiemaweb.com
문서 노드(Document Node)
트리의 최상위에 존재하며 각각 요소, 어트리뷰트, 텍스트 노드에 접근하려면 문서 노드를 통해야 한다. 즉, DOM tree에 접근하기 위한 시작점(entry point)이다.
요소 노드(Element Node)
요소 노드는 HTML 요소를 표현한다. HTML 요소는 중첩에 의해 부자 관계를 가지며 이 부자 관계를 통해 정보를 구조화한다. 따라서 요소 노드는 문서의 구조를 서술한다고 말 할 수 있다. 어트리뷰트, 텍스트 노드에 접근하려면 먼저 요소 노드를 찾아 접근해야 한다. 모든 요소 노드는 요소별 특성을 표현하기 위해 HTMLElement 객체를 상속한 객체로 구성된다. (그림: DOM tree의 객체 구성 참고)
어트리뷰트 노드(Attribute Node)
어트리뷰트 노드는 HTML 요소의 어트리뷰트를 표현한다. 어트리뷰트 노드는 해당 어트리뷰트가 지정된 요소의 자식이 아니라 해당 요소의 일부로 표현된다. 따라서 해당 요소 노드를 찾아 접근하면 어트리뷰트를 참조, 수정할 수 있다.
텍스트 노드(Text Node)
텍스트 노드는 HTML 요소의 텍스트를 표현한다. 텍스트 노드는 요소 노드의 자식이며 자신의 자식 노드를 가질 수 없다. 즉, 텍스트 노드는 DOM tree의 최종단이다.
노드 관련 내용은 아래 문서에서도 확인하실 수 있습니다.
https://dom.spec.whatwg.org/#concept-node
오픈소스 살펴보기 - WebKit 엔진에서의 DOM tree 탐색
DOM tree가 그려지면 우리는 제공되어 있는 DOM API 메서드들을 이용해서 원하는 노드를 선택하거나 수정, 삭제할 수 있습니다. 우리가 필요한 노드를 가져올 때 사용하는 DOM API 메서드에는 여러가지가 있는데, 이번 포스팅에서는 WebKit의 getElementById가 어떻게 구현되어 있는지 중심으로 보려 합니다.
웹 브라우저를 만드는 데 기반을 제공하는 오픈 소스인 WebKit 레포지토리가 있어서 살펴봤는데, 그중 렌더링과 DOM 관련 기능을 제공하는 WebCore 디렉토리 쪽에서 관련 소스를 발견했습니다.
전체 코드는 아래 링크에서 확인하실 수 있습니다.
GitHub - WebKit/WebKit: Home of the WebKit project, the browser engine used by Safari, Mail, App Store and many other applicatio
Home of the WebKit project, the browser engine used by Safari, Mail, App Store and many other applications on macOS, iOS and Linux. - GitHub - WebKit/WebKit: Home of the WebKit project, the browser...
github.com
Element.cpp
// 📨 WebKit/Source/WebCore/dom/Element.cpp
// ...
Element* Element::getElementAttribute(const QualifiedName& attributeName) const
{
// ...
// 🔻 익숙한 이 이름.. 🔻
return treeScope().getElementById(id);
// 🔺 getElementById 🔺
}
// ...
코드가 엄청 많은데, 그 중 getElementById는 TreeScope 클래스 안에 정의되어 있었습니다.
헤더파일을 살펴보니 getElementById란 이름을 가진 오버로딩된 함수 3개를 발견할 수 있었는데, 아마 위에 두 개는 외부에서도 쓸 수 있게 export 해두고 맨 아래 함수는 내부 어딘가에서 쓰겠구나 싶었습니다.
TreeScope.h
// 📨 WebKit/Source/WebCore/dom/TreeScope.h
// ...
WEBCORE_EXPORT Element* getElementById(const AtomString&) const;
WEBCORE_EXPORT Element* getElementById(const String&) const;
Element* getElementById(StringView) const;
// ...
구현부를 살펴보면 아래와 같은데, 함수 하나씩 좀 더 자세히 보려고 합니다.
TreeScope.cpp
📨 WebKit/Source/WebCore/dom/TreeScope.cpp
// ...
Element* TreeScope::getElementById(const AtomString& elementId) const
{
if (elementId.isEmpty())
return nullptr;
if (!m_elementsById)
return nullptr;
return m_elementsById->getElementById(*elementId.impl(), *this);
}
Element* TreeScope::getElementById(const String& elementId) const
{
if (!m_elementsById)
return nullptr;
if (auto atomElementId = AtomStringImpl::lookUp(elementId.impl()))
return m_elementsById->getElementById(*atomElementId, *this);
return nullptr;
}
Element* TreeScope::getElementById(StringView elementId) const
{
if (!m_elementsById)
return nullptr;
if (auto atomElementId = elementId.toExistingAtomString(); !atomElementId.isNull())
return m_elementsById->getElementById(*atomElementId.impl(), *this);
return nullptr;
}
void TreeScope::addElementById(const AtomStringImpl& elementId, Element& element, bool notifyObservers)
{
if (!m_elementsById)
m_elementsById = makeUnique<TreeScopeOrderedMap>();
m_elementsById->add(elementId, element, *this);
if (notifyObservers)
m_idTargetObserverRegistry->notifyObservers(elementId);
}
// ...
TreeScope 클래스를 살펴보니
m_elementsById라는 객체 안에 있는 getElementById 함수가 찐인 것 같았습니다. 이 부분이 우리가 알고싶은 '노드를 찾아서 원하는 엘리먼트를 리턴하는 행위' 인 것 같아 m_elementsById 변수가 처음 할당되는 곳을 찾아가봤습니다. id값을 포함한 엘리먼트가 만들어지고 트리에 추가되는 상황일 것 같아서 관련 부분을 봅니다.
addElementById
m_elementsById가 어떻게 생겼는지 살펴보기 위해 addElementById 과정부터 봅시다.
void TreeScope::addElementById(const AtomStringImpl& elementId, Element& element, bool notifyObservers)
{
if (!m_elementsById)
m_elementsById = makeUnique<TreeScopeOrderedMap>();
m_elementsById->add(elementId, element, *this);
if (notifyObservers)
m_idTargetObserverRegistry->notifyObservers(elementId);
}
참고로 파라미터로 받는 AtomStringImpl 클래스는 WebKit 엔진에서 문자열을 효율적으로 관리하기 위해 만들어졌다고 합니다. 찾아보니 문자열을 Atom으로 매핑하는 형태라고 하는데, 문자열을 Atom으로 매핑한다는 건 문자열을 해시 테이블에 저장하고 이를 Atom으로 대체하는 것을 의미한다고 합니다. 그냥 string 대신 더 빨리 찾을 수 있는 string을 쓴다. 정도로 이해했고, 동일한 Id값을 가진 Element를 여러 번 조회할 때, 즉 같은 문자열이 여러 번 사용될 때 메모리를 절약 + 빠른 검색(해시 테이블 이용하니까)을 가능하게 할 것 같습니다.
wtf/text/AtomString.cpp, wtf/text/WTFString.cpp 파일에 구현부가 있는데, 일단..
다시 돌아와서, 만약 할당된 m_elementsById가 없다면 TreeScopeOrderedMap 타입의 새로운 친구를 만들어서 포인팅하게 합니다. 만들 때 makeUnique 함수를 사용하는데 이는 C++ 스마트 포인터 생성 함수 중 하나로, 동적으로 할당된 객체에 대한 unique_ptr(어떤 객체의 유일한 소유권을 나타내는 포인터)을 생성합니다. makeUnique 함수를 사용하면 후에 할당된 메모리를 해제할 delete를 직접 호출할 필요가 없어 메모리 누수를 방지하고 코드를 간결하게 작성할 수 있습니다.
TreeScope::getElementById
TreeScope 클래스의 getElementById 메서드는 다양한 인자 타입에 대해 오버로딩하고 있습니다. (함수 총 3개) 그렇지만 같은 동작을 수행하고 있습니다.
먼저 첫 번째 getElementById입니다.
Element* TreeScope::getElementById(const AtomString& elementId) const
{
if (elementId.isEmpty())
return nullptr;
if (!m_elementsById)
return nullptr;
return m_elementsById->getElementById(*elementId.impl(), *this);
}AtomString 타입의 elementId를 인자로 받으며, 해당 AtomString 객체를 그대로 사용하여 요소를 찾습니다. 만약 주어진 elementId가 비어있거나 m_elementsById가 없으면 nullptr를 반환하고, 그렇지 않으면 인자로 받은 elementId를 가지고 m_elementsById에서의 getElementById를 호출합니다. 따라서 우리가 원하는 elementId값을 가진 요소를 리턴해줄 수 있게 됩니다.
Element* TreeScope::getElementById(const String& elementId) const
{
if (!m_elementsById)
return nullptr;
if (auto atomElementId = AtomStringImpl::lookUp(elementId.impl()))
return m_elementsById->getElementById(*atomElementId, *this);
return nullptr;
}두 번째도 비슷한 역할을 하는데, 인자 타입이 좀 다릅니다.
String 타입의 elementId를 인자로 받는데, m_elementsById가 있는 경우 먼저 AtomStringImpl::lookUp 함수를 사용하여 elementId를 변환시킨 후 1번 메소드와 같은 단계를 거쳐 (변환된 elementId를 m_elementsById의 getElementById 메서드에 전달) 노드를 찾습니다. 위에서 살펴봤던 것처럼 AtomString을 사용하게 해 더 효율적으로 관리하기 위함으로 보입니다.
Element* TreeScope::getElementById(StringView elementId) const
{
if (!m_elementsById)
return nullptr;
if (auto atomElementId = elementId.toExistingAtomString(); !atomElementId.isNull())
return m_elementsById->getElementById(*atomElementId.impl(), *this);
return nullptr;
}마지막도 같은 맥락인데요, StringView 타입의 elementId를 인자로 받고 있는데 elementId.toExistingAtomString() 함수를 사용하여 변환합니다.
정리하면 오버로딩된 세 함수는 서로 다른 타입의 elementId 값을 AtomString으로 바꾸기 위함이었습니다.
addElementById에서 살펴봤듯이 m_elementsById는 TreeScopeOrderedMap 객체를 가리키고 있는 친구였고, 이 객체 내부에 DOM 트리를 탐색하는 로직이 있는 듯 합니다.
TreeScope 와 TreeScoreOrderedMap
TreeScope 객체와 TreeScoreOrderedMap 객체는 어떤 차이가 있는 걸까 궁금했는데
TreeScope 클래스의 생성자 부분 + 헤더파일을 보니 루트노드, scope를 비롯해 트리의 구조와 관련된 부분들이 정의되어 있더라고요. shadowDOM 트리나 DOM 트리의 뼈대를 나타내는 실질적인 트리 자료구조 부분인 것 같습니다.
여기서 Scope는 뭘 뜻하는 걸까 생각해봤는데, 문서 내 DOM 트리의 범위를 정의한다고 봤습니다. (예를 들면 탐색할 수 있는 범위를 제한해주는? 정해주는?) 각 TreeScope 객체는 고유한 범위가 있고, 그 범위 내에 해당하는 노드들을 해당 TreeScope 객체서 관리해주고 있기 때문에 클래스 이름이 TreeScope가 아닐까 생각합니다. 그래서 DOM 트리의 루트 노드격인 Document 객체가 생성되고 해당하는 TreeScope 객체를 생성하고 관리하면서부터 트리는 시작되는게 아닐까..
반면 TreeScopeOrderedMap에서는 add, remove, get과 같은 실제 연산들 (트리를 탐색하는 과정의 코드)이 작성되어 있었습니다. TreeScope에 속한 노드들을 실제로 저장하고, 검색, 추가, 삭제 등의 연산을 수행하며 최적화하는 작업이 바로 TreeScopeOrderedMap <- 이쪽에서 일어나고 있다고 생각했습니다.
TreeScope.cpp
TreeScope::TreeScope(ShadowRoot& shadowRoot, Document& document)
: m_rootNode(shadowRoot)
, m_documentScope(document)
, m_parentTreeScope(&document)
, m_idTargetObserverRegistry(makeUnique<IdTargetObserverRegistry>())
, m_adoptedStyleSheets(CSSStyleSheetObservableArray::create(shadowRoot))
{
shadowRoot.setTreeScope(*this);
}
TreeScope::TreeScope(Document& document)
: m_rootNode(document)
, m_documentScope(document)
, m_parentTreeScope(nullptr)
, m_idTargetObserverRegistry(makeUnique<IdTargetObserverRegistry>())
, m_adoptedStyleSheets(CSSStyleSheetObservableArray::create(document))
{
document.setTreeScope(*this);
}
TreeScope.h
private:
ContainerNode& m_rootNode;
std::reference_wrapper<Document> m_documentScope;
TreeScope* m_parentTreeScope;
std::unique_ptr<TreeScopeOrderedMap> m_elementsById;
std::unique_ptr<TreeScopeOrderedMap> m_elementsByName;
std::unique_ptr<TreeScopeOrderedMap> m_imageMapsByName;
std::unique_ptr<TreeScopeOrderedMap> m_imagesByUsemap;
std::unique_ptr<TreeScopeOrderedMap> m_labelsByForAttribute;
// ...
TreeScopeOrderedMap
GitHub - WebKit/WebKit: Home of the WebKit project, the browser engine used by Safari, Mail, App Store and many other applicatio
Home of the WebKit project, the browser engine used by Safari, Mail, App Store and many other applications on macOS, iOS and Linux. - GitHub - WebKit/WebKit: Home of the WebKit project, the browser...
github.com
TreeScopeOrderedMap은 앞에서 add, remove, get과 같은 실제 연산들 (트리를 탐색하는 과정의 코드)이 작성되어 있다고 했는데, 실제 TreeScope에 속한 노드들을 저장하고, 검색, 추가, 삭제하는 등의 연산이 일어나기 때문에 최적화가 잘 되어있지 않을까 기대 했습니다. (두근..) TreeScopeOrderedMap 이름처럼 내부에서 Map 형태로 요소 노드들을 관리하고 있는 것 같았는데, 함수가 엄청 많았습니다. 현재 궁금한 건 탐색 과정이니까 그 부분을 중점적으로 보려 합니다.
아까와 마찬가지로 먼저 요소가 저장되는 add 과정부터!
add
void TreeScopeOrderedMap::add(const AtomStringImpl& key, Element& element, const TreeScope& treeScope)
{
RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(&element.treeScope() == &treeScope);
ASSERT_WITH_SECURITY_IMPLICATION(treeScope.rootNode().containsIncludingShadowDOM(&element));
if (!element.isInTreeScope())
return;
Map::AddResult addResult = m_map.ensure(&key, [&element] {
return MapEntry(&element);
});
MapEntry& entry = addResult.iterator->value;
#if ASSERT_ENABLED || ENABLE(SECURITY_ASSERTIONS)
ASSERT_WITH_SECURITY_IMPLICATION(!entry.registeredElements.contains(&element));
entry.registeredElements.add(&element);
#endif
if (addResult.isNewEntry)
return;
RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(entry.count);
entry.element = nullptr;
entry.count++;
entry.orderedList.clear();
}
- key와 element, treeScope 값을 받아 Map에 key-value 쌍을 추가하고 있습니다. 여기서 treeScope는 위에서 살펴봤던 TreeScope 객체에서 this로 자기 자신을 참조합니다.
- element가 treeScope에 속하는지 확인하고, 속하지 않으면 바로 함수를 빠져나가게 됩니다.
- Map의 ensure 함수를 사용하는데, key에 해당하는 value의 존재여부를 확인하는 듯 합니다.
- value가 존재하지 않으면, 새로운 MapEntry 객체를 생성하여 value 값으로 추가합니다.
- value가 이미 존재하고 있다면, 해당 객체의 count를 1 증가시키고 필요한 작업을 해줍니다. (orderedList.clear..)
- 추가된 value 객체의 registeredElements 필드에서 해당 element의 존재 여부를 확인하고, (registeredElements.contains~) 등록되어 있지 않다면 추가하는 과정이 있습니다.
여기서 key값은 AtomStringImpl& 꼴이고, value값은 MapEntry로 element와 관련된 정보를 가리키고 있습니다.
MapEntry에는 어떤 element들이 등록되어 있는지를 가리키는 registeredElements와 몇 개가 총 등록되어 있는지를 나타내는 count 필드 등이 있었는데 이를 보았을 때 해싱 과정에서 키 값이 충돌났을 때 충돌이 발생한 버킷에 체이닝 방식으로 문제를 해결하고 있는 것 같습니다. 동일한 해시 코드를 가진 다른 요소가 등장해도 문제가 없게요.
getElementById
TreeScopeOrderedMap.cpp
Element* TreeScopeOrderedMap::getElementById(const AtomStringImpl& key, const TreeScope& scope) const
{
return get(key, scope, [] (const AtomStringImpl& key, const Element& element) {
return element.getIdAttribute().impl() == &key;
});
}드디어 찐 getElementById 입니다!
getElementById 함수는 key값과 treeScope가 주어지면 그 key에 해당하는 요소를 찾아 반환해주는 함수인데, 이 함수 내부에서 get 함수를 호출해 원하는 결과를 얻어냅니다.
TreeScopeOrderedMap.cpp
template <typename KeyMatchingFunction>
inline Element* TreeScopeOrderedMap::get(const AtomStringImpl& key, const TreeScope& scope, const KeyMatchingFunction& keyMatches) const
{
m_map.checkConsistency();
auto it = m_map.find(&key);
if (it == m_map.end())
return nullptr;
MapEntry& entry = it->value;
ASSERT(entry.count);
if (entry.element) {
auto& element = *entry.element;
RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(&element.treeScope() == &scope);
ASSERT_WITH_SECURITY_IMPLICATION(entry.registeredElements.contains(&element));
return &element;
}
// We know there's at least one node that matches; iterate to find the first one.
for (auto& element : descendantsOfType<Element>(scope.rootNode())) {
if (!element.isInTreeScope())
continue;
if (!keyMatches(key, element))
continue;
entry.element = &element;
RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(&element.treeScope() == &scope);
ASSERT_WITH_SECURITY_IMPLICATION(entry.registeredElements.contains(entry.element));
return &element;
}
#if ASSERT_ENABLED
// FormListedElement may call getElementById to find its owner form in the middle of a tree removal.
if (auto* currentScope = ContainerChildRemovalScope::currentScope()) {
ASSERT(&scope.rootNode() == ¤tScope->parentOfRemovedTree().rootNode());
Node& removedTree = currentScope->removedChild();
ASSERT(is<ContainerNode>(removedTree));
for (auto& element : descendantsOfType<Element>(downcast<ContainerNode>(removedTree))) {
if (!keyMatches(key, element))
continue;
bool removedFromAncestorHasNotBeenCalledYet = element.isConnected();
ASSERT(removedFromAncestorHasNotBeenCalledYet);
return nullptr;
}
}
ASSERT_NOT_REACHED();
#endif // ASSERT_ENABLED
return nullptr;
}get 함수인데, 이 함수는 지정된 key값과 일치하는 MapEntry에 저장된 Element 객체를 반환합니다.
일단 함수의 인자로는 key값, treeScope, keyMatches를 받습니다. key는 찾으려는 Element의 키값이고, scope는 Element가 속한 트리의 범위, keyMatches는 Element의 키를 비교하는 함수입니다. KeyMatchingFunction 타입은 template parameter로 선언되어 있어서, get 함수가 호출될 때 실제 타입이 결정된다는 걸 알 수 있습니다.
큰 흐름만 살펴보면 m_map 에서 key를 검색합니다. m_map에는 등록된 MapEntry들이 있고, 만약 찾는 key값에 해당하는 MayEntry 객체가 없다면 nullptr을 반환합니다. (m_map을 <key: 찾는 키 값 포인터, value: MayEntry>인 요소 노드 정보들을 담고 있는 자료구조이고, 트리를 탐색하기 이전에 빨리 찾게하기 위해 보조해주는 memoization 정도구나, 라고 생각했던 것 같습니다.)
만약 MapEntry 객체가 있고, entry.element가 유효한 경우엔 해당 Element 객체를 반환해 함수를 종료합니다. (찾음)
만약 entry.element가 유효하지 않으면, (1. 해당 MapEntry의 key에 해당하는 값은 존재하지만 value에 해당하는 entry.element가 존재하지 않는 경우, 2. MapEntry의 key는 유효하지만 value에 해당하는 entry.element가 삭제되거나 유효하지 않은 값으로 변경된 경우 등) 트리로 직접 찾으러 나갑니다. (DFS?)
for (auto& element : descendantsOfType<Element>(scope.rootNode())) {
if (!element.isInTreeScope())
continue;
if (!keyMatches(key, element))
continue;
entry.element = &element;
RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(&element.treeScope() == &scope);
ASSERT_WITH_SECURITY_IMPLICATION(entry.registeredElements.contains(entry.element));
return &element;
}
탐색은 get 함수 인자로 들어온 scope (TreeScope)의 루트노드부터 대상으로 정하고 시작합니다 (scope.rootNode()). descendantsOfType(scope.rootNode())는 scope의 루트노드에서 시작하는 모든 하위 객체들 중 Element 타입의 객체들을 DFS 알고리즘으로 탐색하는 과정입니다.
아래는 traverse 방법에 관련된 코드입니다.
// Source/WebCore/dom/TypedElementDescendantIterator.h
template<typename ElementType> ElementDescendantRange<ElementType> descendantsOfType(ContainerNode& root)
{
return ElementDescendantRange<ElementType>(root);
}
// ...
template<typename ElementType> ElementDescendantIterator<ElementType>& ElementDescendantIterator<ElementType>::operator++()
{
ElementIterator<ElementType>::traverseNext();
return *this;
}// Source/WebCore/dom/ElementIterator.h
template <typename ElementType>
inline ElementIterator<ElementType>& ElementIterator<ElementType>::traverseNext()
{
ASSERT(m_current);
ASSERT(!m_assertions.domTreeHasMutated());
m_current = Traversal<ElementType>::next(*m_current, m_root);
#if ASSERT_ENABLED
// Drop the assertion when the iterator reaches the end.
if (!m_current)
m_assertions.dropEventDispatchAssertion();
#endif
return *this;
}
GitHub - WebKit/WebKit: Home of the WebKit project, the browser engine used by Safari, Mail, App Store and many other applicatio
Home of the WebKit project, the browser engine used by Safari, Mail, App Store and many other applications on macOS, iOS and Linux. - GitHub - WebKit/WebKit: Home of the WebKit project, the browser...
github.com
// Source/WebCore/dom/NodeTraversal.cpp
// ...
const Node* ancestor = is<PseudoElement>(current) ? downcast<PseudoElement>(current).hostElement() : current.parentNode();
for (; ancestor; ancestor = ancestor->parentNode()) {
if (ancestor == stayWithin)
return nullptr;
if ((next = ancestor->pseudoAwareNextSibling()))
return next;
}
return nullptr;
// ...
내부를 살펴보면 Traversal::next 함수를 호출하여 다음 노드를 찾는데,
주어진 노드의 부모 노드부터 시작하여, 부모 노드의 다음 형제 노드를 찾을 때까지 조상 노드를 차례대로 거슬러 올라갑니다. 이 때, ancestor 변수는 부모 노드를 가리키며, 조상 노드를 찾기 위해 ancestor 변수를 부모 노드의 부모 노드로 갱신하는 것을 볼 수 있습니다. 이 과정에서 ancestor가 stayWithin 노드와 같아지면, 탐색을 진행하지 않고 nullptr을 반환합니다.
결국 내려갈 때도 거슬러 올라갈 때도 부모-자식 먼저 살펴보고, 형제 노드로 간다는 걸 알 수 있었습니다.
왜 DFS일까 고민해봤는데, 보통 querySelector이나 getElementById 함수의 경우 발견되는 첫 번째 요소노드를 리턴하게 됩니다. 보통 HTML 태그들은 아래와 같이 이루어져있는데, 위에서부터 아래로 차례대로 탐색하여 첫 번째 노드를 리턴하는 과정이 DFS와 유사하다고 느꼈습니다. BFS나 다른 탐색방식은 태그 순서대로 훑는 느낌보다는 형제노드를 왔다갔다할 것 같아서 탐색 과정은 DFS가 선택된게 아닐까.. 추측합니다.
<p>At Mozilla, we're a global community of</p>
<ul>
<li>technologists</li>
<li>thinkers</li>
<li>builders</li>
</ul>
<p>working together…</p>
결국 WebKit에서는 기본적으로 TreeScope는 트리 자료구조로 DOM tree를 관리하고, 이 트리를 보조하는 자료구조로 해시 테이블을 사용합니다. 보조하는 그 자료구조는 TreeScopeOrderedMap라는 클래스로 구현되어 있는데, key-value 꼴로 노드들을 저장해 DFS 트리 탐색 전에 좀 더 빠르게 원하는 요소를 찾을 수 있게 최적화가 되어있습니다.
(참고: https://webkit.org/blog/6/hashtables-part-1/)
마치며
getElementById의 경우에는 Id값을 기준으로 요소를 찾는거라 1대 1 맵핑이 가능하니까 해시 테이블로 최적화를 한 것 같은데, querySelector의 경우에는 또 다른 방식으로 구현되어있을 것 같습니다. getElementById는 트리 탐색 전 해시 테이블을 이용하니 속도가 더 빠르겠다고 생각하기도 했습니다. 또한 관심사별로, 기능별로 잘 분리된 코드 + 어떤 역할을 하는지 쉽게 짐작 가능한 변수명과 함수명을 담은 코드를 보는게 재밌었던 과정이었습니다.
읽어주셔서 감사합니다.
참고자료
https://developer.mozilla.org/ko/docs/Web/Performance/How_browsers_work
'프론트엔드 > 고찰하기' 카테고리의 다른 글
| Javascript의 비동기 프로그래밍 - (2) Promise, async/await 시뮬레이션 (0) | 2023.09.15 |
|---|---|
| Javascript의 비동기 프로그래밍 - (1) 콜백, 뭐라고 생각하세요? (0) | 2023.09.14 |