bendns' repos / rust-analyzer
Unnamed repository; edit this file 'description' to name the repository.
internal: replace TreeSink with a data structure
The general theme of this is to make parser a better independent library. The specific thing we do here is replacing callback based TreeSink with a data structure. That is, rather than calling user-provided tree construction methods, the parser now spits out a very bare-bones tree, effectively a log of a DFS traversal. This makes the parser usable without any *specifc* tree sink, and allows us to, eg, move tests into this crate. Now, it's also true that this is a distinction without a difference, as the old and the new interface are equivalent in expressiveness. Still, this new thing seems somewhat simpler. But yeah, I admit I don't have a suuper strong motivation here, just a hunch that this is better.
Browse Source
Aleksey Kladov 2021-12-26
parent 2f63558 · commit d0d0507
Diffstat
-rw-r--r--crates/mbe/src/syntax_bridge.rs17
-rw-r--r--crates/mbe/src/tt_iter.rs49
-rw-r--r--crates/parser/src/event.rs18
-rw-r--r--crates/parser/src/lib.rs38
-rw-r--r--crates/parser/src/parser.rs3
-rw-r--r--crates/parser/src/tree_traversal.rs67
-rw-r--r--crates/syntax/src/parsing.rs34
-rw-r--r--crates/syntax/src/parsing/reparsing.rs8
-rw-r--r--crates/syntax/src/parsing/text_tree_sink.rs44
-rw-r--r--crates/syntax/src/syntax_node.rs4
10 files changed, 172 insertions, 110 deletions
diff --git a/crates/mbe/src/syntax_bridge.rs b/crates/mbe/src/syntax_bridge.rs
index 109842b0cd..39129b0305 100644
--- a/crates/mbe/src/syntax_bridge.rs
+++ b/crates/mbe/src/syntax_bridge.rs
@@ -1,6 +1,5 @@
//! Conversions between [`SyntaxNode`] and [`tt::TokenTree`].
-use parser::{ParseError, TreeSink};
use rustc_hash::{FxHashMap, FxHashSet};
use syntax::{
ast::{self, make::tokens::doc_comment},
@@ -56,8 +55,18 @@ pub fn token_tree_to_syntax_node(
_ => TokenBuffer::from_subtree(tt),
};
let parser_tokens = to_parser_tokens(&buffer);
+ let tree_traversal = parser::parse(&parser_tokens, entry_point);
let mut tree_sink = TtTreeSink::new(buffer.begin());
- parser::parse(&parser_tokens, &mut tree_sink, entry_point);
+ for event in tree_traversal.iter() {
+ match event {
+ parser::TraversalStep::Token { kind, n_raw_tokens } => {
+ tree_sink.token(kind, n_raw_tokens)
+ }
+ parser::TraversalStep::EnterNode { kind } => tree_sink.start_node(kind),
+ parser::TraversalStep::LeaveNode => tree_sink.finish_node(),
+ parser::TraversalStep::Error { msg } => tree_sink.error(msg.to_string()),
+ }
+ }
if tree_sink.roots.len() != 1 {
return Err(ExpandError::ConversionError);
}
@@ -643,7 +652,7 @@ fn delim_to_str(d: tt::DelimiterKind, closing: bool) -> &'static str {
&texts[idx..texts.len() - (1 - idx)]
}
-impl<'a> TreeSink for TtTreeSink<'a> {
+impl<'a> TtTreeSink<'a> {
fn token(&mut self, kind: SyntaxKind, mut n_tokens: u8) {
if kind == LIFETIME_IDENT {
n_tokens = 2;
@@ -741,7 +750,7 @@ impl<'a> TreeSink for TtTreeSink<'a> {
*self.roots.last_mut().unwrap() -= 1;
}
- fn error(&mut self, error: ParseError) {
+ fn error(&mut self, error: String) {
self.inner.error(error, self.text_pos)
}
}
diff --git a/crates/mbe/src/tt_iter.rs b/crates/mbe/src/tt_iter.rs
index d05e84b0f0..632b591f65 100644
--- a/crates/mbe/src/tt_iter.rs
+++ b/crates/mbe/src/tt_iter.rs
@@ -3,9 +3,8 @@
use crate::{to_parser_tokens::to_parser_tokens, ExpandError, ExpandResult, ParserEntryPoint};
-use parser::TreeSink;
use syntax::SyntaxKind;
-use tt::buffer::{Cursor, TokenBuffer};
+use tt::buffer::TokenBuffer;
macro_rules! err {
() => {
@@ -94,34 +93,28 @@ impl<'a> TtIter<'a> {
&mut self,
entry_point: ParserEntryPoint,
) -> ExpandResult<Option<tt::TokenTree>> {
- struct OffsetTokenSink<'a> {
- cursor: Cursor<'a>,
- error: bool,
- }
-
- impl<'a> TreeSink for OffsetTokenSink<'a> {
- fn token(&mut self, kind: SyntaxKind, mut n_tokens: u8) {
- if kind == SyntaxKind::LIFETIME_IDENT {
- n_tokens = 2;
- }
- for _ in 0..n_tokens {
- self.cursor = self.cursor.bump_subtree();
+ let buffer = TokenBuffer::from_tokens(self.inner.as_slice());
+ let parser_tokens = to_parser_tokens(&buffer);
+ let tree_traversal = parser::parse(&parser_tokens, entry_point);
+
+ let mut cursor = buffer.begin();
+ let mut error = false;
+ for step in tree_traversal.iter() {
+ match step {
+ parser::TraversalStep::Token { kind, mut n_raw_tokens } => {
+ if kind == SyntaxKind::LIFETIME_IDENT {
+ n_raw_tokens = 2;
+ }
+ for _ in 0..n_raw_tokens {
+ cursor = cursor.bump_subtree();
+ }
}
- }
- fn start_node(&mut self, _kind: SyntaxKind) {}
- fn finish_node(&mut self) {}
- fn error(&mut self, _error: parser::ParseError) {
- self.error = true;
+ parser::TraversalStep::EnterNode { .. } | parser::TraversalStep::LeaveNode => (),
+ parser::TraversalStep::Error { .. } => error = true,
}
}
- let buffer = TokenBuffer::from_tokens(self.inner.as_slice());
- let parser_tokens = to_parser_tokens(&buffer);
- let mut sink = OffsetTokenSink { cursor: buffer.begin(), error: false };
-
- parser::parse(&parser_tokens, &mut sink, entry_point);
-
- let mut err = if !sink.cursor.is_root() || sink.error {
+ let mut err = if !cursor.is_root() || error {
Some(err!("expected {:?}", entry_point))
} else {
None
@@ -130,8 +123,8 @@ impl<'a> TtIter<'a> {
let mut curr = buffer.begin();
let mut res = vec![];
- if sink.cursor.is_root() {
- while curr != sink.cursor {
+ if cursor.is_root() {
+ while curr != cursor {
if let Some(token) = curr.token_tree() {
res.push(token);
}
diff --git a/crates/parser/src/event.rs b/crates/parser/src/event.rs
index 41b0328027..ca4c38f2e6 100644
--- a/crates/parser/src/event.rs
+++ b/crates/parser/src/event.rs
@@ -10,9 +10,8 @@
use std::mem;
use crate::{
- ParseError,
+ tree_traversal::TreeTraversal,
SyntaxKind::{self, *},
- TreeSink,
};
/// `Parser` produces a flat list of `Event`s.
@@ -77,7 +76,7 @@ pub(crate) enum Event {
},
Error {
- msg: ParseError,
+ msg: String,
},
}
@@ -88,7 +87,8 @@ impl Event {
}
/// Generate the syntax tree with the control of events.
-pub(super) fn process(sink: &mut dyn TreeSink, mut events: Vec<Event>) {
+pub(super) fn process(mut events: Vec<Event>) -> TreeTraversal {
+ let mut res = TreeTraversal::default();
let mut forward_parents = Vec::new();
for i in 0..events.len() {
@@ -117,15 +117,17 @@ pub(super) fn process(sink: &mut dyn TreeSink, mut events: Vec<Event>) {
for kind in forward_parents.drain(..).rev() {
if kind != TOMBSTONE {
- sink.start_node(kind);
+ res.enter_node(kind);
}
}
}
- Event::Finish => sink.finish_node(),
+ Event::Finish => res.leave_node(),
Event::Token { kind, n_raw_tokens } => {
- sink.token(kind, n_raw_tokens);
+ res.token(kind, n_raw_tokens);
}
- Event::Error { msg } => sink.error(msg),
+ Event::Error { msg } => res.error(msg),
}
}
+
+ res
}
diff --git a/crates/parser/src/lib.rs b/crates/parser/src/lib.rs
index dc02ae6e83..67bc7d9906 100644
--- a/crates/parser/src/lib.rs
+++ b/crates/parser/src/lib.rs
@@ -25,31 +25,19 @@ mod event;
mod parser;
mod grammar;
mod tokens;
+mod tree_traversal;
#[cfg(test)]
mod tests;
pub(crate) use token_set::TokenSet;
-pub use crate::{lexed_str::LexedStr, syntax_kind::SyntaxKind, tokens::Tokens};
-
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub struct ParseError(pub Box<String>);
-
-/// `TreeSink` abstracts details of a particular syntax tree implementation.
-pub trait TreeSink {
- /// Adds new token to the current branch.
- fn token(&mut self, kind: SyntaxKind, n_tokens: u8);
-
- /// Start new branch and make it current.
- fn start_node(&mut self, kind: SyntaxKind);
-
- /// Finish current branch and restore previous
- /// branch as current.
- fn finish_node(&mut self);
-
- fn error(&mut self, error: ParseError);
-}
+pub use crate::{
+ lexed_str::LexedStr,
+ syntax_kind::SyntaxKind,
+ tokens::Tokens,
+ tree_traversal::{TraversalStep, TreeTraversal},
+};
/// rust-analyzer parser allows you to choose one of the possible entry points.
///
@@ -74,11 +62,11 @@ pub enum ParserEntryPoint {
}
/// Parse given tokens into the given sink as a rust file.
-pub fn parse_source_file(tokens: &Tokens, tree_sink: &mut dyn TreeSink) {
- parse(tokens, tree_sink, ParserEntryPoint::SourceFile);
+pub fn parse_source_file(tokens: &Tokens) -> TreeTraversal {
+ parse(tokens, ParserEntryPoint::SourceFile)
}
-pub fn parse(tokens: &Tokens, tree_sink: &mut dyn TreeSink, entry_point: ParserEntryPoint) {
+pub fn parse(tokens: &Tokens, entry_point: ParserEntryPoint) -> TreeTraversal {
let entry_point: fn(&'_ mut parser::Parser) = match entry_point {
ParserEntryPoint::SourceFile => grammar::entry_points::source_file,
ParserEntryPoint::Path => grammar::entry_points::path,
@@ -99,7 +87,7 @@ pub fn parse(tokens: &Tokens, tree_sink: &mut dyn TreeSink, entry_point: ParserE
let mut p = parser::Parser::new(tokens);
entry_point(&mut p);
let events = p.finish();
- event::process(tree_sink, events);
+ event::process(events)
}
/// A parsing function for a specific braced-block.
@@ -119,11 +107,11 @@ impl Reparser {
///
/// Tokens must start with `{`, end with `}` and form a valid brace
/// sequence.
- pub fn parse(self, tokens: &Tokens, tree_sink: &mut dyn TreeSink) {
+ pub fn parse(self, tokens: &Tokens) -> TreeTraversal {
let Reparser(r) = self;
let mut p = parser::Parser::new(tokens);
r(&mut p);
let events = p.finish();
- event::process(tree_sink, events);
+ event::process(events)
}
}
diff --git a/crates/parser/src/parser.rs b/crates/parser/src/parser.rs
index 4c891108a6..4fc734f9c6 100644
--- a/crates/parser/src/parser.rs
+++ b/crates/parser/src/parser.rs
@@ -8,7 +8,6 @@ use limit::Limit;
use crate::{
event::Event,
tokens::Tokens,
- ParseError,
SyntaxKind::{self, EOF, ERROR, TOMBSTONE},
TokenSet, T,
};
@@ -196,7 +195,7 @@ impl<'t> Parser<'t> {
/// structured errors with spans and notes, like rustc
/// does.
pub(crate) fn error<T: Into<String>>(&mut self, message: T) {
- let msg = ParseError(Box::new(message.into()));
+ let msg = message.into();
self.push_event(Event::Error { msg });
}
diff --git a/crates/parser/src/tree_traversal.rs b/crates/parser/src/tree_traversal.rs
new file mode 100644
index 0000000000..4b3a64c85c
--- /dev/null
+++ b/crates/parser/src/tree_traversal.rs
@@ -0,0 +1,67 @@
+//! TODO
+use crate::SyntaxKind;
+
+/// Output of the parser.
+#[derive(Default)]
+pub struct TreeTraversal {
+ /// 32-bit encoding of events. If LSB is zero, then that's an index into the
+ /// error vector. Otherwise, it's one of the thee other variants, with data encoded as
+ ///
+ /// |16 bit kind|8 bit n_raw_tokens|4 bit tag|4 bit leftover|
+ ///
+ event: Vec<u32>,
+ error: Vec<String>,
+}
+
+pub enum TraversalStep<'a> {
+ Token { kind: SyntaxKind, n_raw_tokens: u8 },
+ EnterNode { kind: SyntaxKind },
+ LeaveNode,
+ Error { msg: &'a str },
+}
+
+impl TreeTraversal {
+ pub fn iter(&self) -> impl Iterator<Item = TraversalStep<'_>> {
+ self.event.iter().map(|&event| {
+ if event & 0b1 == 0 {
+ return TraversalStep::Error { msg: self.error[(event as usize) >> 1].as_str() };
+ }
+ let tag = ((event & 0x0000_00F0) >> 4) as u8;
+ match tag {
+ 0 => {
+ let kind: SyntaxKind = (((event & 0xFFFF_0000) >> 16) as u16).into();
+ let n_raw_tokens = ((event & 0x0000_FF00) >> 8) as u8;
+ TraversalStep::Token { kind, n_raw_tokens }
+ }
+ 1 => {
+ let kind: SyntaxKind = (((event & 0xFFFF_0000) >> 16) as u16).into();
+ TraversalStep::EnterNode { kind }
+ }
+ 2 => TraversalStep::LeaveNode,
+ _ => unreachable!(),
+ }
+ })
+ }
+
+ pub(crate) fn token(&mut self, kind: SyntaxKind, n_tokens: u8) {
+ let e = ((kind as u16 as u32) << 16) | ((n_tokens as u32) << 8) | (0 << 4) | 1;
+ self.event.push(e)
+ }
+
+ pub(crate) fn enter_node(&mut self, kind: SyntaxKind) {
+ let e = ((kind as u16 as u32) << 16) | (1 << 4) | 1;
+ self.event.push(e)
+ }
+
+ pub(crate) fn leave_node(&mut self) {
+ let e = 2 << 4 | 1;
+ self.event.push(e)
+ }
+
+ pub(crate) fn error(&mut self, error: String) {
+ let idx = self.error.len();
+ self.error.push(error);
+ let e = (idx as u32) << 1;
+ self.event.push(e);
+ }
+}
diff --git a/crates/syntax/src/parsing.rs b/crates/syntax/src/parsing.rs
index cba1ddde85..6721e5aa81 100644
--- a/crates/syntax/src/parsing.rs
+++ b/crates/syntax/src/parsing.rs
@@ -4,24 +4,18 @@
mod text_tree_sink;
mod reparsing;
-use parser::SyntaxKind;
-use text_tree_sink::TextTreeSink;
-
-use crate::{syntax_node::GreenNode, AstNode, SyntaxError, SyntaxNode};
+use crate::{
+ parsing::text_tree_sink::build_tree, syntax_node::GreenNode, AstNode, SyntaxError, SyntaxNode,
+};
pub(crate) use crate::parsing::reparsing::incremental_reparse;
pub(crate) fn parse_text(text: &str) -> (GreenNode, Vec<SyntaxError>) {
let lexed = parser::LexedStr::new(text);
let parser_tokens = lexed.to_tokens();
-
- let mut tree_sink = TextTreeSink::new(lexed);
-
- parser::parse_source_file(&parser_tokens, &mut tree_sink);
-
- let (tree, parser_errors) = tree_sink.finish();
-
- (tree, parser_errors)
+ let tree_traversal = parser::parse_source_file(&parser_tokens);
+ let (node, errors, _eof) = build_tree(lexed, tree_traversal, false);
+ (node, errors)
}
/// Returns `text` parsed as a `T` provided there are no parse errors.
@@ -34,20 +28,12 @@ pub(crate) fn parse_text_as<T: AstNode>(
return Err(());
}
let parser_tokens = lexed.to_tokens();
+ let tree_traversal = parser::parse(&parser_tokens, entry_point);
+ let (node, errors, eof) = build_tree(lexed, tree_traversal, true);
- let mut tree_sink = TextTreeSink::new(lexed);
-
- // TextTreeSink assumes that there's at least some root node to which it can attach errors and
- // tokens. We arbitrarily give it a SourceFile.
- use parser::TreeSink;
- tree_sink.start_node(SyntaxKind::SOURCE_FILE);
- parser::parse(&parser_tokens, &mut tree_sink, entry_point);
- tree_sink.finish_node();
-
- let (tree, parser_errors, eof) = tree_sink.finish_eof();
- if !parser_errors.is_empty() || !eof {
+ if !errors.is_empty() || !eof {
return Err(());
}
- SyntaxNode::new_root(tree).first_child().and_then(T::cast).ok_or(())
+ SyntaxNode::new_root(node).first_child().and_then(T::cast).ok_or(())
}
diff --git a/crates/syntax/src/parsing/reparsing.rs b/crates/syntax/src/parsing/reparsing.rs
index e9567a838c..dca97a7f58 100644
--- a/crates/syntax/src/parsing/reparsing.rs
+++ b/crates/syntax/src/parsing/reparsing.rs
@@ -10,7 +10,7 @@ use parser::Reparser;
use text_edit::Indel;
use crate::{
- parsing::text_tree_sink::TextTreeSink,
+ parsing::text_tree_sink::build_tree,
syntax_node::{GreenNode, GreenToken, NodeOrToken, SyntaxElement, SyntaxNode},
SyntaxError,
SyntaxKind::*,
@@ -94,11 +94,9 @@ fn reparse_block(
return None;
}
- let mut tree_sink = TextTreeSink::new(lexed);
+ let tree_traversal = reparser.parse(&parser_tokens);
- reparser.parse(&parser_tokens, &mut tree_sink);
-
- let (green, new_parser_errors) = tree_sink.finish();
+ let (green, new_parser_errors, _eof) = build_tree(lexed, tree_traversal, false);
Some((node.replace_with(green), new_parser_errors, node.text_range()))
}
diff --git a/crates/syntax/src/parsing/text_tree_sink.rs b/crates/syntax/src/parsing/text_tree_sink.rs
index c9e7feb965..c435791746 100644
--- a/crates/syntax/src/parsing/text_tree_sink.rs
+++ b/crates/syntax/src/parsing/text_tree_sink.rs
@@ -2,7 +2,7 @@
use std::mem;
-use parser::{LexedStr, ParseError, TreeSink};
+use parser::{LexedStr, TreeTraversal};
use crate::{
ast,
@@ -12,6 +12,36 @@ use crate::{
SyntaxTreeBuilder, TextRange,
};
+pub(crate) fn build_tree(
+ lexed: LexedStr<'_>,
+ tree_traversal: TreeTraversal,
+ synthetic_root: bool,
+) -> (GreenNode, Vec<SyntaxError>, bool) {
+ let mut builder = TextTreeSink::new(lexed);
+
+ if synthetic_root {
+ builder.start_node(SyntaxKind::SOURCE_FILE);
+ }
+
+ for event in tree_traversal.iter() {
+ match event {
+ parser::TraversalStep::Token { kind, n_raw_tokens } => {
+ builder.token(kind, n_raw_tokens)
+ }
+ parser::TraversalStep::EnterNode { kind } => builder.start_node(kind),
+ parser::TraversalStep::LeaveNode => builder.finish_node(),
+ parser::TraversalStep::Error { msg } => {
+ let text_pos = builder.lexed.text_start(builder.pos).try_into().unwrap();
+ builder.inner.error(msg.to_string(), text_pos);
+ }
+ }
+ }
+ if synthetic_root {
+ builder.finish_node()
+ }
+ builder.finish_eof()
+}
+
/// Bridges the parser with our specific syntax tree representation.
///
/// `TextTreeSink` also handles attachment of trivia (whitespace) to nodes.
@@ -28,7 +58,7 @@ enum State {
PendingFinish,
}
-impl<'a> TreeSink for TextTreeSink<'a> {
+impl<'a> TextTreeSink<'a> {
fn token(&mut self, kind: SyntaxKind, n_tokens: u8) {
match mem::replace(&mut self.state, State::Normal) {
State::PendingStart => unreachable!(),
@@ -70,11 +100,6 @@ impl<'a> TreeSink for TextTreeSink<'a> {
State::Normal => (),
}
}
-
- fn error(&mut self, error: ParseError) {
- let text_pos = self.lexed.text_start(self.pos).try_into().unwrap();
- self.inner.error(error, text_pos);
- }
}
impl<'a> TextTreeSink<'a> {
@@ -106,11 +131,6 @@ impl<'a> TextTreeSink<'a> {
(node, errors, is_eof)
}
- pub(super) fn finish(self) -> (GreenNode, Vec<SyntaxError>) {
- let (node, errors, _eof) = self.finish_eof();
- (node, errors)
- }
-
fn eat_trivias(&mut self) {
while self.pos < self.lexed.len() {
let kind = self.lexed.kind(self.pos);
diff --git a/crates/syntax/src/syntax_node.rs b/crates/syntax/src/syntax_node.rs
index c95c76c0a8..b96f10c173 100644
--- a/crates/syntax/src/syntax_node.rs
+++ b/crates/syntax/src/syntax_node.rs
@@ -69,7 +69,7 @@ impl SyntaxTreeBuilder {
self.inner.finish_node();
}
- pub fn error(&mut self, error: parser::ParseError, text_pos: TextSize) {
- self.errors.push(SyntaxError::new_at_offset(*error.0, text_pos));
+ pub fn error(&mut self, error: String, text_pos: TextSize) {
+ self.errors.push(SyntaxError::new_at_offset(error, text_pos));
}
}