Roslyn SyntaxNodes có được tái sử dụng không?

Question

Tôi đã tham gia một cái nhìn để Roslyn CTP và, trong khi nó giải quyết một vấn đề tương tự như Expression tree API, cả hai đều bất biến nhưng Roslyn làm như vậy theo một cách hoàn toàn khác:

• Expression nút không có tham chiếu đến nút cha, được sửa đổi bằng cách sử dụng ExpressionVisitor và đó là lý do tại sao các phần lớn có thể được sử dụng lại.

• Roslyn's SyntaxNode, ở phía bên kia, có tham chiếu đến cha mẹ của nó, vì vậy tất cả các nút có hiệu quả trở thành một khối không thể tái sử dụng. Các phương thức như Update, ReplaceNode, v.v., được cung cấp để thực hiện các sửa đổi.

Điều này kết thúc ở đâu? Document? Project? ISolution? API thúc đẩy thay đổi từng bước của cây (thay vì nút lên), nhưng mỗi bước có tạo bản sao đầy đủ không?

Tại sao họ lại chọn lựa như vậy? Có một số mẹo thú vị tôi đang thiếu?

Answer 1

CẬP NHẬT: Câu hỏi này là the subject of my blog on June 8th, 2012. Cảm ơn vì câu hỏi tuyệt vời của bạn!

---

Câu hỏi hay. Chúng tôi tranh luận về các vấn đề bạn đã nêu ra trong một thời gian dài.

Chúng tôi muốn có một cấu trúc dữ liệu mà có những đặc điểm sau đây:

• Immutable.
• Hình thức của một cái cây.
• Truy cập giá rẻ vào các nút cha mẹ từ các nút con.
• Có thể ánh xạ từ một nút trong cây tới độ lệch ký tự trong văn bản.
• Persistent.

By kiên trì Tôi có nghĩa là khả năng tái sử dụng hầu hết các nút hiện có trong cây khi chỉnh sửa được thực hiện để bộ đệm văn bản. Vì các nút là không thay đổi nên không có rào cản để tái sử dụng chúng. Chúng tôi cần điều này cho hiệu suất; chúng tôi không thể phân tích cú pháp lại các wodges lớn của tệp mỗi lần bạn nhấn một phím. Chúng ta cần phải tái lex và phân tích lại chỉ các phần của cây bị ảnh hưởng bởi bản chỉnh sửa.

Bây giờ khi bạn cố gắng để đưa tất cả năm trong những điều đó vào một cấu trúc dữ liệu bạn ngay lập tức chạy vào các vấn đề:

• Làm thế nào để bạn xây dựng một nút ở nơi đầu tiên? Cha mẹ và đứa trẻ đều đề cập đến nhau, và không thay đổi, vì vậy cái nào được xây dựng đầu tiên?
• Giả sử bạn quản lý để giải quyết vấn đề đó: làm thế nào để bạn làm cho nó liên tục? Bạn không thể tái sử dụng một nút con trong một phụ huynh khác vì điều đó sẽ liên quan đến việc nói với đứa trẻ rằng nó có một phụ huynh mới. Nhưng đứa trẻ là bất biến.
• Giả sử bạn quản lý để giải quyết vấn đề đó: khi bạn chèn một ký tự mới vào bộ đệm chỉnh sửa, vị trí tuyệt đối của mỗi nút được ánh xạ tới một vị trí sau điểm đó thay đổi. Điều này làm cho việc tạo một cấu trúc dữ liệu liên tục trở nên rất khó khăn, bởi vì bất kỳ chỉnh sửa nào cũng có thể thay đổi các nhịp của hầu hết các nút!

Nhưng trong nhóm Roslyn, chúng tôi thường xuyên làm những việc không thể. Chúng tôi thực sự làm điều không thể bằng cách giữ hai cây phân tích. Cây "xanh" không thay đổi, liên tục, không có tham chiếu gốc, được tạo từ "từ dưới lên" và mỗi nút theo dõi chiều rộng nhưng không phải là vị trí tuyệt đối. Khi chỉnh sửa xảy ra, chúng tôi chỉ xây dựng lại các phần của cây xanh bị ảnh hưởng bởi bản chỉnh sửa, thường là về O (log n) của tổng số nút phân tích cú pháp trong cây.

Cây "đỏ" là mặt tiền bất biến được xây dựng xung quanh cây xanh; nó được xây dựng "từ trên xuống" theo yêu cầu và bị bỏ đi trên mọi chỉnh sửa. Nó tính toán tài liệu tham khảo của phụ huynh bằng cách sản xuất theo yêu cầu khi bạn đi qua cây từ đầu trang. Nó sản xuất các vị trí tuyệt đối bằng cách tính toán chúng từ độ rộng, một lần nữa, khi bạn hạ xuống.

Bạn, người dùng, chỉ nhìn thấy cây đỏ; cây xanh là một chi tiết thực hiện. Nếu bạn nhìn vào trạng thái bên trong của một nút phân tích cú pháp, bạn sẽ thấy rằng có một tham chiếu đến một nút phân tích cú pháp khác trong đó có một loại khác; đó là nút cây xanh.

Ngẫu nhiên, chúng được gọi là "cây xanh/đỏ" vì đó là các màu đánh dấu bảng trắng mà chúng tôi đã sử dụng để vẽ cấu trúc dữ liệu trong cuộc họp thiết kế. Không có ý nghĩa nào khác đối với màu sắc.

Lợi ích của chiến lược này là chúng tôi có được tất cả những điều tuyệt vời đó: bất biến, kiên trì, tham chiếu gốc và v.v. Chi phí là hệ thống này phức tạp và có thể tiêu tốn rất nhiều bộ nhớ nếu mặt tiền "đỏ" lớn. Hiện tại chúng tôi đang thực hiện các thử nghiệm để xem liệu chúng tôi có thể giảm một số chi phí mà không làm mất lợi ích hay không.