- 나만의 텍스트 편집기를 만들기 위해, 직접 텍스트 데이터 구조를 만들어 보는 과정.
- 텍스트 편집기는 거대한 파일을 편집하거나, 다중 커서, 실행/취소 등 다양한 기능에 의해 그 구조를 만들기가 매우 어려움.
- 이에 데이터 구조에 요구되는 기능은 다음과 같음.
- 효율적인 삽입/삭제
- 효율적인 실행 취소/다시 실행
- UTF-8 인코딩을 사용 가능
- 효율적인 다중 커서 편집
- Gap Buffer는 구현이 간단하지만, 실행 취소와 다중 커서 기능을 구현하기 매우 어려움.
- Rope는 큰 파일을 작은 크기로 분할하여 수정이 가능해 효율적이지만, 실행 취소 기능을 위해선 오버헤드가 커지고 메모리 사용량이 예상보다 많이 늘어날 수 있음.
- Piece Table은 Microsoft Word에서 사용했을 정도로 효율적인 구조지만, 편집을 많이 할 경우 성능이 저하되고 실행 취소를 위해 메모리 사용량이 늘어날 수 있음.
- Piece Tree는 위의 모든 단점을 해결하기 위해 VSCode 팀에서 구현한 텍스트 편집기를 위한 가장 좋은 데이터 구조임.
- Rope와 Piece Table의 장점만을 골라 구현함.
- 조각 간의 연결을 위해 RB Tree를 쓰기 때문에 많은 편집이 있더라도 여전히 효율적임.
- 다만 VSCode 팀에서 구현한 버전은 불변 데이터 구조가 아니기 때문에 실행 취소 기능에서 약간의 비효율성을 가짐.
- 데이터 구조에 불변성을 추가해 모든 문제를 해결한 새로운 Piece Tree를 구현하기로 함.
- 전통적인 RB 트리는 불변성을 줄 수 없어 Bartosz Milewski가 구현한 불변 RB 트리를 참조하여 구현 시작.
- VSCode 팀에서 구현한 구조와 차이점은 다음과 같음.
- 에디터가 Carriage Return 문자를 고려해야 하는 경우가 적기 때문에 CRLF를 별도로 기록하지 않음.
- 디버깅을 위해 전체 버퍼를 반복자와 같은 형태로 확인할 수 있는 API를 추가함.
- 데이터 구조가 불변이기 때문에 실행 취소/다시 실행이 아주 간단함.
- 삭제 기능을 구현하는 것이 가장 어려웠지만, 결국 구현에 성공함.
- 새로 작성한 데이터 구조를 fredbuf라는 이름으로 공개함.