나는 Roslyn CTP를 살펴 보았고 , Expression tree API 와 비슷한 문제를 해결 하지만 둘 다 불변이지만 Roslyn은 상당히 다른 방식으로 그렇게합니다.
-
Expression노드는 부모 노드에 대한 참조가없고 a를 사용하여 수정되므로ExpressionVisitor큰 부분을 재사용 할 수 있습니다. -
반면에 Roslyn의
SyntaxNode는 부모를 참조하므로 모든 노드는 효과적으로 재사용이 불가능한 블록이됩니다. 방법은 좋아Update,ReplaceNode등, 수정을 위해 제공됩니다.
이것은 어디에서 끝나는가? Document? Project? ISolution? API는 (버튼을 누르는 대신) 트리의 단계별 변경을 촉진하지만 각 단계가 전체 사본을 생성합니까?
그들은 왜 그런 선택을 했습니까? 내가 놓친 흥미로운 속임수가 있습니까?
답변
업데이트 :이 질문은 2012 년 6 월 8 일 내 블로그의 주제였습니다 . 좋은 질문에 감사드립니다!
좋은 질문입니다. 우리는 당신이 제기 한 문제에 대해 오랫동안 토론했습니다.
다음과 같은 특성을 가진 데이터 구조를 원합니다.
- 불변.
- 나무의 형태.
- 하위 노드에서 상위 노드에 저렴한 액세스.
- 트리의 노드에서 텍스트의 문자 오프셋으로 매핑 할 수 있습니다.
- 영구 .
에 의해 지속성 내가 할 수있는 능력을 의미 트리에서 기존 노드의 대부분을 다시 편집은 텍스트 버퍼에 이루어질 때를. 노드는 변경 불가능하므로 재사용에 대한 장벽이 없습니다. 성능을 위해 이것이 필요합니다. 우리는 당신이 키를 누를 때마다 파일의 거대한 덩어리를 재분석 할 수 없습니다. 편집의 영향을받은 트리 부분 만 re-lex 및 re-parse해야합니다.
이제이 다섯 가지를 모두 하나의 데이터 구조에 넣으려고하면 즉시 문제가 발생합니다.
- 처음에 노드를 어떻게 구축합니까? 부모와 자식은 모두 서로를 참조하고 불변이므로 어느 것이 먼저 빌드됩니까?
- 당신이 그 문제를 해결할 수 있다고 가정 해보자 : 어떻게 그것을 지속적으로 만들 수 있는가? 다른 부모의 자식 노드를 재사용 할 수 없습니다. 자식에게 새 부모가 있다는 것을 알리는 것이 포함되기 때문입니다. 그러나 아이는 불변입니다.
- 이 문제를 해결할 수 있다고 가정하면 새 문자를 편집 버퍼에 삽입하면 해당 지점 이후 위치에 매핑되는 모든 노드 의 절대 위치가 변경됩니다. 어떤 편집도 대부분의 노드의 범위를 변경할 수 있기 때문에 영구 데이터 구조를 만드는 것이 매우 어렵습니다!
그러나 Roslyn 팀에서는 일상적으로 불가능한 일을합니다. 우리는 실제로 두 개의 파스 트리 를 유지함으로써 불가능한 일을합니다 . “녹색”트리는 변경 불가능하고 영구적이며 상위 참조가 없으며 “상향식”으로 빌드되며 모든 노드는 너비를 추적 하지만 절대 위치 는 추적 하지 않습니다 . 편집이 발생하면 편집의 영향을받은 녹색 트리 부분 만 다시 빌드합니다. 일반적으로 트리의 전체 구문 분석 노드 중 약 O (log n)입니다.
“빨간색”나무는 녹색 나무 주위에 지어진 불변의 정면 입니다. 필요 에 따라 “하향식” 으로 빌드 되고 편집 할 때마다 버려집니다. 트리를 통해 맨 위에서 내려갈 때 요청시이를 제조하여 상위 참조를 계산합니다 . 하강 할 때 폭에서 다시 계산하여 절대 위치를 제조합니다.
사용자 인 당신은 붉은 나무 만 볼 수 있습니다. 그린 트리는 구현 세부 사항입니다. 구문 분석 노드의 내부 상태를 살펴보면 실제로 다른 유형의 다른 구문 분석 노드에 대한 참조가 있음을 알 수 있습니다 . 이것이 녹색 트리 노드입니다.
덧붙여서, 이것들은 우리가 디자인 회의에서 데이터 구조를 그리는 데 사용한 화이트 보드 마커 색상 이었기 때문에 “빨강 / 녹색 나무”라고 불립니다. 색상에는 다른 의미가 없습니다.
이 전략의 이점은 우리가 불변성, 지속성, 부모 참조 등 모든 위대한 것들을 얻을 수 있다는 것입니다. 비용은이 시스템이 복잡하고 “빨간색”파사드가 커지면 많은 메모리를 소비 할 수 있다는 것입니다. 현재 우리는 혜택을 잃지 않고 비용을 줄일 수 있는지 확인하기 위해 실험을하고 있습니다.
