텍스트 에디터 자료구조: Immutable Piece Tree 구현기

게시일: 2025년 11월 22일 | 원문 작성일: 2023년 6월 8일 | 저자: Cameron DaCamara | 원문 보기

들어가며

텍스트 에디터를 프로그래밍하는 건 흥미로운 도전이에요. 텍스트 에디터가 해결해야 하는 문제들은 사소한 것부터 엄청나게 어려운 것까지 다양하죠. 최근 저는 제가 만들고 있는 에디터의 내부 자료구조를 재작업하는 여정을 시작했어요. 구체적으로는 모든 텍스트 에디터의 가장 기본적인 자료구조인 텍스트 자체를 다루는 구조 말이에요.

왜?

텍스트 에디터를 처음부터 만드는 훌륭한 리소스가 이미 많은데 (오늘날 이미 훌륭한 텍스트 에디터들도 존재하고), 제가 왜 이 글을 쓸까요? 몇 가지 이유가 있어요:

1. 이전에 시도해본 적 없는 종류의 프로젝트에 도전하고 싶었어요
2. 실제로 사용할 수 있는 도구를 만들고 싶었어요
3. 자체 자료구조를 구축하는 것을 더 많이 다뤄보고 싶었어요

저는 특별히 제 프로그램에서 관찰한 문제를 해결하고 필요한 유연성을 제공하기 위해 자체 자료구조를 구현하는 과정을 거쳤어요. 기성 솔루션으로는 제 우려사항을 정확히 해결할 수 없었거든요. 더 나아가, 자체 텍스트 에디터를 작성하는 전체 프로젝트는 Handmade Community에서 영감을 받았기 때문에 모든 것이 처음부터 만들어져요. 여기서 기존 솔루션을 사용했다면 에디터가 만들어진 정신을 배신하는 느낌이었을 거예요.

처음에는… 거대한 문자열

저는 “실험하고 가능한 한 빨리 작동시키기”를 강력히 믿어요 - 본질적으로 빨리 실패하는 정신이죠. 이게 첫 시도에서 최적화를 무시하라는 뜻은 아니에요. 저는 코드를 의도적으로 악화시키는 걸 거부해요. 그래서 가능한 가장 간단한 텍스트 파일 표현부터 시작했어요: 거대한 하나의 문자열.

단일 문자열을 텍스트 버퍼로 사용하는 건 꽤 좋은 속성들이 있어요:

1. 가능한 가장 압축된 표현이에요
2. 삽입과 삭제 알고리즘이 단순해요
3. 렌더링 프로세스에 친화적이에요. 추가 할당 없이 문자열을 뷰로 나눠서 독립적으로 렌더링할 수 있거든요
4. 단순하다고 말했나요?

하지만, 오, 단점은 정말 크게 다가와요. 1MB 이상의 파일을 다루고 싶다면? 행운을 빌어요. 선형 시간 연산들이 정말 체감되기 시작할 뿐만 아니라, 일부 편집 후 기본 버퍼가 재할당되어야 한다면 전체 프로세스가 엄청나게 느려져요. 더 큰 버퍼를 할당하고 각 바이트를 새 버퍼로 복사한 다음 이전 버퍼를 삭제해야 하니까요. O(n) 연산이 무작위로 O(n²)으로 변할 수 있어요.

또 다른 미묘한 단점이 있어요: undo/redo를 어떻게 구현할까요? 가장 명백한 접근은 모든 개별 삽입과 삭제를 추적하는 별도의 자료구조를 만드는 거예요. 삽입은 추적하기 쉬워요. 오프셋 범위로 저장하고 undo 연산이 호출되면 원본 버퍼에서 버리면 되거든요. 삭제는 좀 더 까다로워요. 거대 문자열 접근에서는 제거된 문자를 포함하는 작은 버퍼와 추출된 오프셋을 실제로 저장해야 해요. 이런 식으로 작동할 수는 있지만 지나치게 복잡하고 큰 텍스트를 삭제할 때 잠재적으로 큰 할당 오버헤드가 필요해요. 더 나은 방법이 있을 거예요…

조사 단계

저는 거대한 텍스트 버퍼가 가진 모든 문제를 해결하고 싶었어요. 구체적인 목표는 다음과 같아요:

1. 효율적인 삽입/삭제
2. 효율적인 undo/redo
3. UTF-8 인코딩을 가능하게 할 충분한 유연성
4. 효율적인 멀티커서 편집

Gap Buffer

처음에는 gap buffer 경로로 가기 시작했어요. Gap buffer는 구현하기 매우 간단하고 Emacs가 gap buffer를 자료구조로 사용하는 걸로 유명하죠. Gap buffer는 격리된 편집에 대해 첫 번째 목표를 꽤 잘 해결해요. 한 번에 파일 전체를 편집하는 경우는 그리 흔하지 않잖아요? 음… 꼭 그렇지만은 않아요. 제가 좋아하는 현대 텍스트 에디터의 기능 중 하나가 멀티커서 편집이거든요 (블록 스타일 편집이라고도 불리지만 약간 다르긴 해요). Chris Wellons의 “Gap Buffers Are Not Optimized for Multiple Cursors”를 읽은 후 (이 글에는 gap buffer를 설명하는 최고의 애니메이션 중 하나가 있어요), gap buffer가 틀린 길이라는 확신을 얻었어요. 멀티커서 편집이 제게 중요하니까요.

Gap buffer는 또한 큰 문자열 표현과 유사한 문제가 있어요. 효율적인 undo/redo가 많은 추가 저장공간/자료구조 없이는 어려워요.

평가: Gap buffer는 탈락.

Rope

Rope는 텍스트 에디터에 매우 매력적인 자료구조가 될 수 있어요. Rope는 특히 편집에 좋은 많은 속성을 가지고 있는데, 파일을 여러 작은 할당으로 나누기 때문에 파일 어느 지점에서든 매우 빠른 amortized 삽입이나 삭제가 가능해요 - O(lg n). 처음 보면 rope가 제 초기 우려사항을 모두 해결하는 것처럼 보여요. undo/redo 같은 연산을 트리 스냅샷 (또는 제거되거나 변경된 노드 유지)으로 더 쉽게 구현할 수 있고, 멀티커서 편집이 훨씬 가벼운 연산이 되거든요.

그럼 함정은 뭘까요? undo/redo를 다시 살펴봐요.

가장 매력적인 rope 자료구조 버전은 전체를 불변(immutable)으로 만드는 거예요. 이는 텍스트를 포함하는 노드를 확장할 때 실제로는 새 버퍼로 새 노드를 생성하거나 추가 콘텐츠만 담을 새 노드를 생성한다는 뜻이에요. 둘 다 똑같이 낭비처럼 보이네요 (rope는 각 노드의 크기를 제한하는 상수를 정의해야 해요). Copy-on-write로 노드를 복사한다는 건 undo 스택이 원본 트리의 경량 버전을 포함하는 동안, 새로 구성된 트리가 총 메모리 소비를 생각보다 훨씬 더 확장할 수 있다는 뜻이에요.

제 에디터 목적으로는 좀 더 가벼운 것을 원했어요.

평가: Rope는 문제를 완전히 해결하지 못함.

Piece Table

이제 흥미로워지네요. Piece table은 텍스트 에디터와 긴 역사를 가진 자료구조예요. Microsoft Word가 한때 빠른 undo/redo와 효율적인 파일 저장 같은 기능을 구현하기 위해 piece table을 사용했죠. Piece table은 제게 많은 체크박스를 표시하는 것처럼 보여요.

한 가지, 아마도 약간의 단점이 있어요. 전통적인 piece table이 연속적인 과거 편집 배열로 구현된다는 사실 때문에, 긴 편집 세션에서 같은 파일에 많은 작은 편집을 추가하면 거대 텍스트 버퍼에서 봤던 아티팩트들이 나타나기 시작할 수 있어요. 이뿐만 아니라 undo/redo 스택도 이 잠재적으로 큰 항목 배열을 저장해야 해요.

평가: Piece table은 긴 세션에서 한계가 있음.

Piece Tree

VSCode 팀이 piece tree를 구현해서 문제를 해결했어요. VSCode 블로그에서 텍스트 버퍼 재구현에 대해 다룬 모든 걸 되풀이하고 싶진 않지만, 왜 이 특정 버전의 piece table이 그렇게 흥미로운지, 그리고 제가 빠진 부분을 메우기 위해 무엇을 변경해야 했는지는 다루고 싶어요.

편집 주: VSCode 팀이 piece tree를 발명한 건 아니에요. 개별 조각을 표현하기 위해 트리를 활용하는 건 1998년 “Data Structures for Text Sequences” 논문에서 제안되었어요. 저는 단지 이 논문에서 제안된 아이디어의 VSCode 구현이 고품질이고 잘 테스트되었다고 생각했어요.

VSCode가 구현한 piece table은 마치 전통적인 piece table과 rope 자료구조가 아기를 낳았고, 그 아기가 모든 면에서 부모를 능가한 것 같아요. Rope 같은 삽입 amortization 비용의 모든 아름다움과 piece table의 메모리 압축을 얻을 수 있어요. Piece tree는 개별 조각을 저장하기 위해 red-black tree(RB tree)를 사용해서 빠르고 압축된 삽입 시간을 달성해요. 이 자료구조가 유용한 이유는 균형 잡힌 탐색 트리라는 보장이 시간이 지나 조각이 추가되더라도 O(lg n) 탐색 시간을 유지할 수 있게 해주기 때문이에요.

단 하나의 작은 조각만 빠졌어요… VSCode 구현은 불변 자료구조를 사용하지 않아요. 즉, undo/redo 스택을 캡처하려면 전체 piece tree를 복사해야 한다는 뜻이에요 (물론 기본 데이터는 아니에요). 그래서 piece table의 단점이 일부 있네요. 그냥 고치면 되겠죠! 얼마나 어려울까요? (스포일러: 어려웠어요).

최종 달성 목표:

1. 효율적인 삽입/삭제 ✓
2. 효율적인 undo/redo (불변성으로) ✓
3. 유연한 UTF-8 인코딩 지원 ✓
4. 효율적인 멀티커서 편집 ✓

나만의 Piece Tree

나만의 piece tree를 구현하는 주요 목표는 순수 함수형 자료구조로 만드는 거였어요. 즉, 텍스트의 기본 뷰가 완전히 불변이고 변경하려면 새로운 부분 트리가 필요하다는 뜻이죠.

VSCode가 구현한 piece tree는 전통적인 RB tree를 사용해요. Introduction to Algorithms 책을 다시 꺼낸 후 빠르게 깨달았어요. 책에 설명된 RB tree를 순수 함수형 변형으로 재구현하려는 건 두 가지 이유로 쉽지 않을 거라고요:

1. 책이 NIL 노드를 나타내는 sentinel 노드를 많이 사용하는데, 일반 노드처럼 변경될 수 있어요. 단, 하나만 있죠
2. 책의 알고리즘이 각 노드의 부모 포인터를 많이 사용해요. 순수 함수형 자료구조에서 부모 포인터는 안 돼요. 트리 어디서든 변경하면 본질적으로 전체 트리가 무효화되거든요

누군가는 불변 RB tree를 구현했을 거예요, 맞죠? 알고 보니… 네? 어느 정도는요? 검색 중에 Bartosz Milewski의 “Functional Data Structures in C++: Trees”를 찾았어요. 여기서 순수 함수형 RB tree를 구현하는 간단한 방법을 다루는데, 삽입만이에요. 삽입은 필수적이지만 삭제도 필요해요. 삭제가 없으면 piece tree는 작동하지 않아요. 댓글에서 삭제가 어렵다고, 매우 어렵고 종종 새로운 노드 개념이 필요하다고 논의되었어요. 저는 Milewski가 삽입에 취한 접근을 정말 좋아했기 때문에 이 자료구조로 RB tree를 시작했고 나머지 piece tree를 그 주변에 구현했어요. 삭제는 제외하고요. 나중에 다시 다룰게요.

제가 다른 점

이제 텍스트 버퍼를 트리로 구현하면서, 제 여정을 수용하고 제 특정 문제를 해결하기 위해 구현의 어떤 부분을 변경해야 하는지 평가하기 위해 강력한 디버깅 도구를 설계하는 게 극도로 중요했어요.

CRLF

새 구현이 VSCode 버전과 크게 다르지는 않아요. 제가 다르기 시작하는 부분은 CRLF 줄 끝을 트리의 공식 개념으로 성문화하지 않기로 한 결정이에요. 저는 CRLF가 단일 조각 내에 포함되도록 하는 그들 구현의 회피책이 마음에 들지 않았어요. 제 생각엔 소수의 시나리오에서만 실제로 고려해야 하는 기능에 대해 자료구조를 엄청나게 복잡하게 만드는 것 같았거든요.

디버깅

복잡한 자료구조를 디버그할 수 있는 것은 어떤 진전을 이루려면 필수적이에요. VSCode 구현의 독립 실행형 repo를 보면 버퍼 내용을 검증하는 주요 방법이 __CODE_UNDER_0__를 통한 것임을 알 수 있어요. 이건 기본적이고 중요한 API예요. 전체 버퍼를 실제로 확인하는 목적으로는 다른 접근이 필요했어요. 그래서 iterator 같은 인터페이스로 tree walker를 설계했고 for-each 루프를 사용할 수 있게 했어요:

__FENCED_UNDER_0__

이 walker는 편집과 삭제를 검증하는 데 매우 귀중했고, 주어진 오프셋에서 특정 코드포인트를 걸을 수 있는 능력이 필요했기 때문에 UTF-8 지원이 올바른지 확인할 추가 공간을 열어줬어요.

Undo/Redo

VSCode 구현은 텍스트 버퍼 연산으로 undo/redo를 직접 구현하지 않았어요. 텍스트 버퍼에 적용된 편집이 이전 편집을 되돌리는 데 필요한 일련의 ‘역’ 연산을 기록하고 이를 호출자에게 전달하는 시스템을 통해 했어요. 호출자는 이 정보를 저장하고 역 편집을 순차적으로 적용할 책임이 있죠. 이 시스템은 확실히 한 가지 접근이고 전체 트리를 다시 복사하는 것을 피하지만, 단일 문자열 구현으로 undo/redo를 할 수 있다고 가정한 것처럼 데이터 버퍼를 할당하는 데 의존해요. 제 undo/redo 루틴은 이래요:

__FENCED_UNDER_1__

네, 필요한 게 전부예요. 두 개의 linked list와 __CODE_UNDER_1__ 호출 (O(lg n) 연산). 전체 자료구조가 불변일 때 이전에 참조를 저장한 어떤 루트로든 되돌릴 수 있고 에디터 상태가 완전히 일관성 있을 거예요. 이건 에디터 상태 그래프를 탐색할 수 있는 분기 에디터 상태 UI (미니 소스 제어 시스템처럼)를 만들 가능성을 열어줘요. 더 이상 나중에 되돌려야 하는 지저분한 커밋은 없어요!

삭제 재검토

삭제 연산을 다시 다루겠다고 했어요. 텍스트 에디터에 관해 이야기할 때 삽입 연산만큼 기본적이니까요. 불변 RB tree 삭제를 구현하는 경로로 갈 때, 솔직히 여러 번 포기할 뻔했어요. 알고리즘 책에 언급된 알고리즘은 sentinel 노드도 제거하면서 부모 포인터에 의존하지 않는 재귀 버전으로 변환해야 했기 때문에 실행 가능하지 않았어요 (VSCode의 RB tree 구현은 sentinel 노드를 사용하는데, 반드시 나쁜 건 아니에요).

RB tree 삭제가 왜 어려운지 대략 알려면 전통적인 RB tree 삭제가 다뤄야 하는 경우를 살펴봐야 해요. 특히 빨간색 노드를 삭제해서 double-black 위반을 도입하는 경우는 많은 오류 여지를 남겨요. 다행히도, 다른 누군가가 불변 RB tree를 구현하는 게 유용하다고 생각했고 persistent-rbtree를 찾았어요. 이건 실제로 Rust Persistent Data Structures에서 적응된 거예요. 이 코드에는 제 기존 RB tree에 적용할 수 있는 신뢰할 수 있는 노드 삭제 로직이 있었고, 제 삭제 루틴의 기초가 되었어요.

마침내, 삭제를 구현한 후 완벽한 자료구조 (저자의 목적에 맞는)가 모든 목표를 달성하며 완성되었어요.

fredbuf

여기까지 왔는데 보여줄 코드가 없다면 미쳤을 거예요. ‘fred’는 제 텍스트 에디터의 이름이고, VSCode textbuffer를 충분히 수정하고 ‘fred’에 맞게 적응시켰기 때문에 ‘fredbuf’라고 불렀어요. fredbuf repo에서 모든 코드와 테스트를 볼 수 있어요. 서드파티 라이브러리 요구사항이 없어서 빌드가 가능한 한 간단해요. MIT 라이선스이니, 마음껏 사용하세요! 제가 생각한 것보다 더 개선하세요! repo는 C++20을 지원하는 C++ 컴파일러만 필요해요.

언젠가 ‘fred’도 공개할 수도 있어요.

결론

이것으로부터 무엇을 배웠을까요?

1. 사전 조사와 제약사항 식별은 절대적으로 필수적이에요. 복잡한 자료구조가 문제를 해결하지 못한다는 걸 구현의 고통을 겪은 후에 발견하고 싶진 않을 거예요
2. 자료구조를 위한 디버깅 유틸리티를 매우 초기에 만드세요. 처음부터 강력한 디버깅 유틸리티를 만들지 않았다면 이 프로젝트를 완료하지 못했을 거라고 확신해요
3. Immutable RB tree 삭제는 어려워요!

텍스트 에디터 설계, C++ 언어, 또는 컴파일러에도 관심이 있다면 Twitter에서 대화해요. 저는 항상 다른 사람들에게 유용할 수 있는 지식을 배우고 공유하는 데 관심이 있어요.

다음에 또 만나요!