Emacs의 저수준 tree-sitter 통합 설계를 깊이 있게 다룹니다. Lisp/C API, 내로잉과 지연 파싱, 편집–파싱 라이프사이클, 간접 버퍼 등의 주제를 설명합니다.
1편, 기초
Emacs의 저수준 tree-sitter 통합이 자리를 잡아가고 있어서, 설계를 한 번 훑어보려 합니다. 이는 문서 보완 1이자 호기심 많은 해커들을 위한 (바라건대) 흥미로운 읽을거리입니다.
소스에 매우 자세한 문서를 써 두었지만, 글 한 편이 더 읽기 쉬울 수도 있겠죠? 그리고 곁다리 이야기들도 더 담을 수 있고요.
tree-sitter 통합은 대략 두 부분으로 나눌 수 있습니다. 저수준 C API 통합과 고수준 응용 통합입니다. 이 글은 전자만 다룹니다. 고수준 통합은 다음 글에서 이야기하겠습니다.
Emacs에서 tree-sitter를 어떻게 "사용"하는지에 관심이 있다면 아래 글들을 순서대로 읽는 걸 권합니다. 인터넷에도 좋은 자료가 많습니다.
우리가 공개한 Lisp API는 고수준 언어에 맞게 단순화되었을 뿐, 대부분 C API와 동일합니다. C 함수의 절반 정도는 Lisp API에 짝이 있습니다.
C API는 파스 트리 객체(TSTree)를 노출하지만, 저는 이를 Lisp에는 노출하지 않기로 했습니다. 정말 필요하지 않기 때문입니다. 파서의 루트 노드를 얻는 함수(treesit-parser-root-node)만 노출하면 됩니다. 게다가 트리 객체는 관리가 많이 필요해서 노출하면 골칫거리가 큽니다.
트리 탐색을 위한 TSCursor도 노출하지 않았습니다. 이것 역시 저수준 기능이고, Lisp API를 복잡하게 만들 뿐 아니라 관리가 필요하며, Lisp 세계에 의미 있는 가치를 더하지 않습니다. 통합 코드 내부에서는 광범위하게 사용하지만, Lisp 레벨에서는 커서가 정말로 필요하지 않습니다. 커서 없이 파스 트리를 순회할 때도 매 단계마다 Lisp 노드를 하나 생성하는데—그 자체로 충분히 빠르고 병목이 되지 않습니다. 게다가 대부분의 경우 노드에 어떤 Lisp 프레디킷이나 연산을 실행해야 하므로 어차피 Lisp 노드를 생성해야 합니다.
Tree-sitter의 C API는 타임아웃과 취소 플래그를 설정할 수 있습니다. Emacs는 사실상 동시성이 없기 때문에 자연스럽게 생략되었습니다. 설령 Emacs에 동시성이 생긴다 해도 Lisp API에는 넣지 않을 생각입니다—Emacs의 작업 부하에서는 그것들이 얻어주는 성능상의 이점이 추가되는 복잡도에 비해 가치가 크지 않습니다.
❦
초기 2022년 구현에서 큰 모서리를 잘라 갔던 부분도 있습니다. Emacs가 버퍼 편집 내용을 tree-sitter에 전달할 때, tree-sitter API가 요구하는 줄(line)과 열(column) 위치를 보내지 않았습니다.
그 이유는 Emacs가 텍스트를 저장하는 데 갭 버퍼를 사용해서 Emacs에서 줄과 열 위치를 효율적으로 얻기가 2 어렵기 때문입니다. 또한 tree-sitter가 사실상 줄·열 위치를 필요로 하지 않기 때문이기도 합니다. tree-sitter는 그것들을 내부에서 대개 전달만 하다가, API 호출자가 노드의 줄·열 위치 같은 것을 요구할 때 최종적으로 그대로 뱉어낼 뿐입니다. 그래서 우리는 더미 줄·열 값을 넘기고, 노드의 줄·열 위치는 아예 묻지 않았습니다.
더미 값을 넘긴다고 해서 문제가 전혀 없었던 것은 아닙니다. tree-sitter가 줄·열 위치가 이상한 값일 거라고 예상하지 못해 생긴 "버그"를 몇 번 겪었습니다. 하지만 Amaan Qureshi께서 우리가 말썽을 부렸으니 벌을 받아도 할 말 없는 상황임에도 불구하고, 기꺼이 그 이슈들을 고쳐 주셨습니다 :-)
3년이 지난 지금 우리는 드디어 줄·열 추적을 추가했고, 사실상 오버헤드는 없으며 Emacs 31에 실릴 예정입니다. 이건 이것만으로 별도 글이 필요하니 여기서는 자세히 다루지 않겠습니다.
Emacs에 줄·열 추적을 추가하자는 논의도 있지만, 실제로 될지, 된다면 언제 될지 모르겠습니다. 아이디어는 이렇습니다. 우리는 이미 버퍼에 바이트 위치와 문자 위치를 캐시해 빠르게 상호 변환할 수 있도록 여러 마커를 유지하고 있습니다. 여기에 줄 번호도 캐시에 더하면 임의 위치의 줄 번호를 빠르게 얻을 수 있다는 것이죠.
독자분들은 아마 Emacs의 내로잉(narrowing)을 알고 계실 겁니다. 사용자(와 Lisp)는 버퍼의 특정 구간으로 "내로우"할 수 있고, 그 구간 밖의 버퍼 내용은 Emacs의 모든 것에게 존재하지 않는 것으로 취급됩니다. 우리는 tree-sitter가 내로잉을 존중하도록 만들기로 했습니다.
선택지는 둘이었습니다. 하나는 tree-sitter가 내로잉을 무시하고 항상 전체 버퍼를 보도록 두는 것입니다. 개인적으로는 매우 솔깃합니다. 구현이 아주 직선적이고, tree-sitter가 보는 것과 내로잉 상태를 동기화하는 온갖 골치거리를 피할 수 있으니까요. 또한 tree-sitter가 내로잉을 존중하면 내로잉이 tree-sitter의 증분 파싱을 망치지 않을까 걱정됐습니다—Emacs에서는 작은 영역으로 내로우했다가 작업을 하고 다시 넓히는(widen) 패턴이 흔하고, 자주 일어납니다. 이는 실제 변경된 부분만 파싱하지 않고 버퍼 전체를 계속 다시 파싱하게 만들 수도 있습니다.
하지만 tree-sitter가 내로잉을 무시하도록 두면 심각한 문제가 생깁니다. tree-sitter가 내로잉을 무시하면, 사실상 내로잉을 사용자 수준의 시각적 편의로 취급하는 셈인데, Emacs는 내로잉을 그렇게 취급하지 않습니다. Emacs는 내로잉을 기본적인 추상화로 봅니다.3 내로우된 영역 밖에 접근하는 것은 Lisp에서 엄격히 금지되며, 오류를 신호합니다. 거의 모든 코드(Lisp과 C)는 자신이 내로우된 영역 안에서 동작한다는 가정하에 작성됩니다. tree-sitter가 전체 버퍼를 본다면, 반환하기 전에 모든 것이 경계를 벗어나지 않았는지 확인하기 위한 후처리가 필요합니다. 또한 노드가 내로잉 경계를 가로지르는 등의 에지 케이스도 생길 것입니다. 머리 아파요!
동시에, 성능에 대한 걱정은 약간의 요령으로 깔끔하게 해결할 수 있습니다. 곧 살펴보겠습니다.
내로잉을 사용자 수준과 저수준으로 분리하자는 논의/토론이 있기는 하지만, 당분간은 Emacs에서 내로잉이 기본 추상화라는 사실은 변하지 않을 것입니다.
❦
Eli는 tree-sitter가 내로잉을 존중해야 한다는 입장이 매우 확고했고, 옳았습니다. 또한 재파싱을 지연(lazy)시키자는 점도 확고했습니다—파스 트리를 실제로 사용할 때만 재파싱하자는 것입니다.
처음엔 이 점에 대해 저도 뚜렷한 의견이 없었습니다. 한편으로는 변경이 들어오자마자 바로 파싱해서 증분 파싱의 이점을 최대한 살리고, 짧은 멈춤 여러 번으로 긴 멈춤 한 번을 대체하고 싶습니다. 하지만 다른 한편으로 대부분의 시간에 우리는 키 입력마다 리디스플레이를 하므로, 사실상 매 키 입력마다 재파싱하고 있는 셈이기도 합니다.
나중에 알게 된 사실은, 우리의 상황—내로잉과 tree-sitter의 시야를 동기화해야 하는 상황—에서는 지연 파싱이 오히려 설계를 단순하게 만들어 준다는 것입니다. 그리고 지연 파싱은 제가 가졌던 성능상의 걱정도 멋지게 해소해 줍니다.
어떻게 작동하는지 봅시다.
가장 낮은 수준에서는, 버퍼 텍스트에 대한 변경은 insdel.c의 열댓 개 함수와 casefiddle.c, editfns.c의 몇몇 함수에서 이루어집니다. 이 함수들에서 우리는 tree-sitter에게 변경을 알리지만(treesit_record_change), 아직 재파싱은 하지 않습니다. 각 변경은 3-튜플 형태입니다: 변경된 영역의 시작 위치, 변경 전 끝 위치, 변경 후 끝 위치.
내로잉을 지원하기 위해, 각 tree-sitter 파서의 "뷰포트(viewport)"를 파서 객체에 기록해 둡니다. 기본적으로 파서가 현재 보고 있는 버퍼 범위의 시작과 끝 위치를 기록합니다. 버퍼 변경을 tree-sitter에 전달할 때는, 변경 위치를 tree-sitter의 뷰포트에 맞도록 잘라야 하고, 삽입/삭제로 인해 뷰포트가 늘거나 줄 때는 버퍼 내에서 뷰포트의 위치도 갱신해야 합니다.
삭제의 경우는 간단합니다—삭제된 범위가 뷰포트와 겹치면, 그 겹치는 부분만 파서로 보냅니다. 그리고 뷰포트는 시작을 앞으로 당기거나 끝을 뒤로 밀어 줄어듭니다.
############################# -> 전체 버퍼 [ ] -> 파서의 뷰포트 DDDDDDDDDD -> 이 부분을 삭제 DDDDDD -> 파서는 이 부분만 본다 [ ] -> 새 뷰포트
삽입의 경우는 삽입 위치에 따라 다릅니다. 뷰포트 이전에 삽입되면 뷰포트를 그대로 이동시키면 됩니다. 뷰포트 내부에 삽입되면 전체를 파서에 전달하고 그만큼 뷰포트를 확장합니다. 뷰포트 이후의 삽입은 파서가 보지 못합니다.
가장 일반적인 경우는 "삭제 후 삽입"으로 생각할 수 있습니다. 실제 코드에서는 삭제와 삽입을 하나의 편집으로 결합합니다. 결합 로직이 있어도 구현은 매우 단순합니다. 변경의 start, old_end, new_end 위치를 뷰포트로 클리핑하고, 뷰포트 시작이 얼마나 이동하는지 계산한 다음, 이것들을 더해 뷰포트의 새 끝을 구합니다. 어려운 부분은 이것이 올바른 동작임을 스스로 납득하는 것입니다. 여기서 "삭제 후 삽입"이라는 개념이 도움이 됩니다.
❦
지연 파싱이 있기 때문에, 실제로 사용자가 파스 트리에서 노드를 요청할 때에만 재파싱합니다(treesit_ensure_parsed).
tree-sitter가 모든 버퍼 편집을 알고 있다는 것은 확실하지만, 파서에 재파싱을 요청하기 전에 내로잉 상태를 동기화해야 합니다. 사용자가 버퍼를 내로우하고 다시 넓힐 때, 우리는 tree-sitter에 업데이트를 보내지 않는다는 점에 주목하십시오. 사용자가 파서에 접근하는 시점까지 기다렸다가 내로잉을 동기화합니다. 이것이 앞서 언급한 성능 저하를 피하는 방법입니다. 가령 지금 파서는 넓혀진 버퍼를 보고 있고, 어떤 Lisp가 버퍼를 내로우해서 작업을 하고 다시 넓혔다고 합시다. 파서는 그 모든 것을 행복하게도 전혀 모릅니다. 그 "작업"이 버퍼 편집을 포함했다 해도 괜찮습니다. 변경은 기존과 같이 파서의 뷰포트로 클리핑되어 전달됩니다. 중요한 점은, Lisp가 내로우했다 넓힐 때 버퍼의 큰 부분을 재파싱하지 않는다는 것입니다.
어떤 Lisp가 내로우된 버퍼에서 파스 트리에 접근해야 한다면, 그 용도의 전용 파서를 하나 만들면 됩니다. 전역 파서는 항상 넓혀진 버퍼를 보고, 내로우 전용 파서는 항상 내로우된 버퍼를 봅니다.
내로잉 동기화(treesit_sync_visible_region)도 간단합니다. 우리는 두 개의 범위를 가지고 있습니다—버퍼의 내로잉 범위와 파서의 뷰포트입니다. 파서의 뷰포트를 내로잉 범위에 맞추기 위해 파서에 인위적인 "버퍼 변경"을 보내면 됩니다. 세 단계로 합니다. 첫째, 뷰포트의 시작이 내로잉의 시작과 일치하거나 그보다 앞서도록 만듭니다. 만약 뷰포트의 시작이 내로잉보다 뒤라면, 그 차이만큼을 파서에 "삽입"합니다.
###ABCD####################### -> 전체 버퍼 { } -> 이 범위로 내로우됨 [ ] -> 파서의 뷰포트 [ ] -> 파서에 "ABCD"를 "삽입"
둘째, 뷰포트의 끝이 내로잉의 끝과 일치하도록 파서에 "삽입"하거나 파서에서 "삭제"합니다. 셋째, 다시 뷰포트의 시작이 내로잉의 시작과 일치하도록, 마찬가지로 "삽입" 또는 "삭제"합니다. 이 세 단계 접근법은 두 범위의 가능한 모든 배치를 처리할 수 있으며, 각 경우를 따로따로 다룰 필요가 없습니다. 다시 말하지만, 모든 경우에 잘 작동한다는 점을 스스로 납득하는 것이 어려운 부분입니다.
그 다음 파서에 재파싱을 요청하면 됩니다. 이렇게 해서 버퍼 편집에서 파서 재파싱으로 이어지는 한 사이클이 끝납니다.
간접 버퍼는 Emacs에서 덜 알려진 기능입니다. 어떤 버퍼에서든 M-x clone-indirect-buffer RET를 호출하면 현재 버퍼의 간접 버퍼가 만들어집니다. 간접 버퍼와 원본 버퍼는 동일한 버퍼 내용을 공유하지만, 그 외에는 완전히 별개의 버퍼로, 각자의 버퍼 로컬 변수, 오버레이 등을 가집니다.
tree-sitter 측면에서는, 간접 버퍼들과 원본 버퍼가 파서 목록을 공유하는 것이 자연스럽습니다. 이렇게 하면 어느 버퍼에서 변경이 일어나든 모든 파서가 업데이트되며, 이는 버퍼 내용이 공유되는 것과 동일합니다. 하지만 treesit-parser-list에서 약간의 필터링을 하여, 마치 각 버퍼가 자신의 파서 목록을 가진 것처럼 보이게 합니다. 전체 목록을 반환하는 대신, 주어진 버퍼에서 생성된 파서들만 반환합니다.
tree-sitter 통합과 관련해 emacs-devel에 질문을 올렸던 원래 스레드를 찾았습니다. 조용히 tree-sitter 작업을 시작했던 기억이 있습니다. 두어 달에 한 번씩 tree-sitter 통합 논의가 있었지만 아무 일도 일어나지 않았고, 저는 expand-region에 tree-sitter가 필요하다고 생각했거든요. 그래서 "그냥 바인딩 하나 넣자, 얼마나 어렵겠어?"라고 생각했습니다.
2022년에 tree-sitter 작업을 시작했다고 생각했는데, 실제로는 2021년만큼 이른 시점에 시작했더군요. 그 스레드들을 다시 보니, 당시 저는 많은 것들에 대해 정말 아무것도 몰랐습니다. 다행히도 메일링 리스트의 많은 분들(Eli, Stefan, 그리고 정말 많은 분들)이 매우 인내심 있게 도와주셨고, 수백 통의 이메일을 주고받으며 통합이 점차 형태를 갖추었습니다. 지금 와서 생각하면, 제가 정기적으로 Emacs에 기여하게 되었고, 한때는 버그 트래커 4에서 어떤 달에는 두 번째로 많은 메시지를 답장하기도 했다는 게 미치도록 놀랍습니다 ;-)
말할 필요도 없지만, 제가 tree-sitter 작업의 일부만 했을 뿐이고, 수많은 멋진 분들이 훌륭한 기능들을 기여하셨습니다. 저는 저수준 통합 작업만 했고, 다른 것들은 대부분 다른 분들이 하셨습니다. 여기에 모든 분을 나열해 보려고 했지만, 기억을 더듬을수록 명단이 계속 늘어나서, 결국 누구라도 빠뜨릴까 봐 포기했습니다 :-(
버그 트래커 얘기가 나와서 말인데, 제가 debbugs.gnu.org에서 #40000 버그 보고를 올렸던 거 아시나요? :-))))
