diff options
Diffstat (limited to 'crates/ra_syntax/src/parser_impl')
-rw-r--r-- | crates/ra_syntax/src/parser_impl/event.rs | 154 | ||||
-rw-r--r-- | crates/ra_syntax/src/parser_impl/input.rs | 86 | ||||
-rw-r--r-- | crates/ra_syntax/src/parser_impl/mod.rs | 194 |
3 files changed, 434 insertions, 0 deletions
diff --git a/crates/ra_syntax/src/parser_impl/event.rs b/crates/ra_syntax/src/parser_impl/event.rs new file mode 100644 index 000000000..9fd56b996 --- /dev/null +++ b/crates/ra_syntax/src/parser_impl/event.rs | |||
@@ -0,0 +1,154 @@ | |||
1 | //! This module provides a way to construct a `File`. | ||
2 | //! It is intended to be completely decoupled from the | ||
3 | //! parser, so as to allow to evolve the tree representation | ||
4 | //! and the parser algorithm independently. | ||
5 | //! | ||
6 | //! The `Sink` trait is the bridge between the parser and the | ||
7 | //! tree builder: the parser produces a stream of events like | ||
8 | //! `start node`, `finish node`, and `FileBuilder` converts | ||
9 | //! this stream to a real tree. | ||
10 | use std::mem; | ||
11 | use { | ||
12 | lexer::Token, | ||
13 | parser_impl::Sink, | ||
14 | SyntaxKind::{self, TOMBSTONE}, | ||
15 | }; | ||
16 | |||
17 | |||
18 | /// `Parser` produces a flat list of `Event`s. | ||
19 | /// They are converted to a tree-structure in | ||
20 | /// a separate pass, via `TreeBuilder`. | ||
21 | #[derive(Debug)] | ||
22 | pub(crate) enum Event { | ||
23 | /// This event signifies the start of the node. | ||
24 | /// It should be either abandoned (in which case the | ||
25 | /// `kind` is `TOMBSTONE`, and the event is ignored), | ||
26 | /// or completed via a `Finish` event. | ||
27 | /// | ||
28 | /// All tokens between a `Start` and a `Finish` would | ||
29 | /// become the children of the respective node. | ||
30 | /// | ||
31 | /// For left-recursive syntactic constructs, the parser produces | ||
32 | /// a child node before it sees a parent. `forward_parent` | ||
33 | /// exists to allow to tweak parent-child relationships. | ||
34 | /// | ||
35 | /// Consider this path | ||
36 | /// | ||
37 | /// foo::bar | ||
38 | /// | ||
39 | /// The events for it would look like this: | ||
40 | /// | ||
41 | /// | ||
42 | /// START(PATH) IDENT('foo') FINISH START(PATH) COLONCOLON IDENT('bar') FINISH | ||
43 | /// | /\ | ||
44 | /// | | | ||
45 | /// +------forward-parent------+ | ||
46 | /// | ||
47 | /// And the tree would look like this | ||
48 | /// | ||
49 | /// +--PATH---------+ | ||
50 | /// | | | | ||
51 | /// | | | | ||
52 | /// | '::' 'bar' | ||
53 | /// | | ||
54 | /// PATH | ||
55 | /// | | ||
56 | /// 'foo' | ||
57 | /// | ||
58 | /// See also `CompletedMarker::precede`. | ||
59 | Start { | ||
60 | kind: SyntaxKind, | ||
61 | forward_parent: Option<u32>, | ||
62 | }, | ||
63 | |||
64 | /// Complete the previous `Start` event | ||
65 | Finish, | ||
66 | |||
67 | /// Produce a single leaf-element. | ||
68 | /// `n_raw_tokens` is used to glue complex contextual tokens. | ||
69 | /// For example, lexer tokenizes `>>` as `>`, `>`, and | ||
70 | /// `n_raw_tokens = 2` is used to produced a single `>>`. | ||
71 | Token { | ||
72 | kind: SyntaxKind, | ||
73 | n_raw_tokens: u8, | ||
74 | }, | ||
75 | |||
76 | Error { | ||
77 | msg: String, | ||
78 | }, | ||
79 | } | ||
80 | |||
81 | |||
82 | pub(super) fn process<'a, S: Sink<'a>>(builder: &mut S, tokens: &[Token], mut events: Vec<Event>) { | ||
83 | fn tombstone() -> Event { | ||
84 | Event::Start { kind: TOMBSTONE, forward_parent: None } | ||
85 | } | ||
86 | let eat_ws = |idx: &mut usize, builder: &mut S| { | ||
87 | while let Some(token) = tokens.get(*idx) { | ||
88 | if !token.kind.is_trivia() { | ||
89 | break; | ||
90 | } | ||
91 | builder.leaf(token.kind, token.len); | ||
92 | *idx += 1 | ||
93 | } | ||
94 | }; | ||
95 | |||
96 | let events: &mut [Event] = &mut events; | ||
97 | let mut depth = 0; | ||
98 | let mut forward_parents = Vec::new(); | ||
99 | let mut next_tok_idx = 0; | ||
100 | for i in 0..events.len() { | ||
101 | match mem::replace(&mut events[i], tombstone()) { | ||
102 | Event::Start { | ||
103 | kind: TOMBSTONE, .. | ||
104 | } => (), | ||
105 | |||
106 | Event::Start { kind, forward_parent } => { | ||
107 | forward_parents.push(kind); | ||
108 | let mut idx = i; | ||
109 | let mut fp = forward_parent; | ||
110 | while let Some(fwd) = fp { | ||
111 | idx += fwd as usize; | ||
112 | fp = match mem::replace(&mut events[idx], tombstone()) { | ||
113 | Event::Start { | ||
114 | kind, | ||
115 | forward_parent, | ||
116 | } => { | ||
117 | forward_parents.push(kind); | ||
118 | forward_parent | ||
119 | }, | ||
120 | _ => unreachable!(), | ||
121 | }; | ||
122 | } | ||
123 | for kind in forward_parents.drain(..).rev() { | ||
124 | if depth > 0 { | ||
125 | eat_ws(&mut next_tok_idx, builder); | ||
126 | } | ||
127 | depth += 1; | ||
128 | builder.start_internal(kind); | ||
129 | } | ||
130 | } | ||
131 | Event::Finish => { | ||
132 | depth -= 1; | ||
133 | if depth == 0 { | ||
134 | eat_ws(&mut next_tok_idx, builder); | ||
135 | } | ||
136 | |||
137 | builder.finish_internal(); | ||
138 | } | ||
139 | Event::Token { | ||
140 | kind, | ||
141 | mut n_raw_tokens, | ||
142 | } => { | ||
143 | eat_ws(&mut next_tok_idx, builder); | ||
144 | let mut len = 0.into(); | ||
145 | for _ in 0..n_raw_tokens { | ||
146 | len += tokens[next_tok_idx].len; | ||
147 | next_tok_idx += 1; | ||
148 | } | ||
149 | builder.leaf(kind, len); | ||
150 | } | ||
151 | Event::Error { msg } => builder.error(msg), | ||
152 | } | ||
153 | } | ||
154 | } | ||
diff --git a/crates/ra_syntax/src/parser_impl/input.rs b/crates/ra_syntax/src/parser_impl/input.rs new file mode 100644 index 000000000..c0fe4d488 --- /dev/null +++ b/crates/ra_syntax/src/parser_impl/input.rs | |||
@@ -0,0 +1,86 @@ | |||
1 | use {lexer::Token, SyntaxKind, SyntaxKind::EOF, TextRange, TextUnit}; | ||
2 | |||
3 | use std::ops::{Add, AddAssign}; | ||
4 | |||
5 | pub(crate) struct ParserInput<'t> { | ||
6 | text: &'t str, | ||
7 | start_offsets: Vec<TextUnit>, | ||
8 | tokens: Vec<Token>, // non-whitespace tokens | ||
9 | } | ||
10 | |||
11 | impl<'t> ParserInput<'t> { | ||
12 | pub fn new(text: &'t str, raw_tokens: &'t [Token]) -> ParserInput<'t> { | ||
13 | let mut tokens = Vec::new(); | ||
14 | let mut start_offsets = Vec::new(); | ||
15 | let mut len = 0.into(); | ||
16 | for &token in raw_tokens.iter() { | ||
17 | if !token.kind.is_trivia() { | ||
18 | tokens.push(token); | ||
19 | start_offsets.push(len); | ||
20 | } | ||
21 | len += token.len; | ||
22 | } | ||
23 | |||
24 | ParserInput { | ||
25 | text, | ||
26 | start_offsets, | ||
27 | tokens, | ||
28 | } | ||
29 | } | ||
30 | |||
31 | pub fn kind(&self, pos: InputPosition) -> SyntaxKind { | ||
32 | let idx = pos.0 as usize; | ||
33 | if !(idx < self.tokens.len()) { | ||
34 | return EOF; | ||
35 | } | ||
36 | self.tokens[idx].kind | ||
37 | } | ||
38 | |||
39 | pub fn len(&self, pos: InputPosition) -> TextUnit { | ||
40 | let idx = pos.0 as usize; | ||
41 | if !(idx < self.tokens.len()) { | ||
42 | return 0.into(); | ||
43 | } | ||
44 | self.tokens[idx].len | ||
45 | } | ||
46 | |||
47 | pub fn start(&self, pos: InputPosition) -> TextUnit { | ||
48 | let idx = pos.0 as usize; | ||
49 | if !(idx < self.tokens.len()) { | ||
50 | return 0.into(); | ||
51 | } | ||
52 | self.start_offsets[idx] | ||
53 | } | ||
54 | |||
55 | pub fn text(&self, pos: InputPosition) -> &'t str { | ||
56 | let idx = pos.0 as usize; | ||
57 | if !(idx < self.tokens.len()) { | ||
58 | return ""; | ||
59 | } | ||
60 | let range = TextRange::offset_len(self.start_offsets[idx], self.tokens[idx].len); | ||
61 | &self.text[range] | ||
62 | } | ||
63 | } | ||
64 | |||
65 | #[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)] | ||
66 | pub(crate) struct InputPosition(u32); | ||
67 | |||
68 | impl InputPosition { | ||
69 | pub fn new() -> Self { | ||
70 | InputPosition(0) | ||
71 | } | ||
72 | } | ||
73 | |||
74 | impl Add<u32> for InputPosition { | ||
75 | type Output = InputPosition; | ||
76 | |||
77 | fn add(self, rhs: u32) -> InputPosition { | ||
78 | InputPosition(self.0 + rhs) | ||
79 | } | ||
80 | } | ||
81 | |||
82 | impl AddAssign<u32> for InputPosition { | ||
83 | fn add_assign(&mut self, rhs: u32) { | ||
84 | self.0 += rhs | ||
85 | } | ||
86 | } | ||
diff --git a/crates/ra_syntax/src/parser_impl/mod.rs b/crates/ra_syntax/src/parser_impl/mod.rs new file mode 100644 index 000000000..b343b404f --- /dev/null +++ b/crates/ra_syntax/src/parser_impl/mod.rs | |||
@@ -0,0 +1,194 @@ | |||
1 | mod event; | ||
2 | mod input; | ||
3 | |||
4 | use std::cell::Cell; | ||
5 | |||
6 | use { | ||
7 | lexer::Token, | ||
8 | parser_api::Parser, | ||
9 | parser_impl::{ | ||
10 | event::{process, Event}, | ||
11 | input::{InputPosition, ParserInput}, | ||
12 | }, | ||
13 | TextUnit, | ||
14 | }; | ||
15 | |||
16 | use SyntaxKind::{self, EOF, TOMBSTONE}; | ||
17 | |||
18 | pub(crate) trait Sink<'a> { | ||
19 | type Tree; | ||
20 | |||
21 | fn new(text: &'a str) -> Self; | ||
22 | |||
23 | fn leaf(&mut self, kind: SyntaxKind, len: TextUnit); | ||
24 | fn start_internal(&mut self, kind: SyntaxKind); | ||
25 | fn finish_internal(&mut self); | ||
26 | fn error(&mut self, err: String); | ||
27 | fn finish(self) -> Self::Tree; | ||
28 | } | ||
29 | |||
30 | /// Parse a sequence of tokens into the representative node tree | ||
31 | pub(crate) fn parse_with<'a, S: Sink<'a>>( | ||
32 | text: &'a str, | ||
33 | tokens: &[Token], | ||
34 | parser: fn(&mut Parser), | ||
35 | ) -> S::Tree { | ||
36 | let events = { | ||
37 | let input = input::ParserInput::new(text, tokens); | ||
38 | let parser_impl = ParserImpl::new(&input); | ||
39 | let mut parser_api = Parser(parser_impl); | ||
40 | parser(&mut parser_api); | ||
41 | parser_api.0.into_events() | ||
42 | }; | ||
43 | let mut sink = S::new(text); | ||
44 | process(&mut sink, tokens, events); | ||
45 | sink.finish() | ||
46 | } | ||
47 | |||
48 | /// Implementation details of `Parser`, extracted | ||
49 | /// to a separate struct in order not to pollute | ||
50 | /// the public API of the `Parser`. | ||
51 | pub(crate) struct ParserImpl<'t> { | ||
52 | inp: &'t ParserInput<'t>, | ||
53 | |||
54 | pos: InputPosition, | ||
55 | events: Vec<Event>, | ||
56 | steps: Cell<u32>, | ||
57 | } | ||
58 | |||
59 | impl<'t> ParserImpl<'t> { | ||
60 | pub(crate) fn new(inp: &'t ParserInput<'t>) -> ParserImpl<'t> { | ||
61 | ParserImpl { | ||
62 | inp, | ||
63 | |||
64 | pos: InputPosition::new(), | ||
65 | events: Vec::new(), | ||
66 | steps: Cell::new(0), | ||
67 | } | ||
68 | } | ||
69 | |||
70 | pub(crate) fn into_events(self) -> Vec<Event> { | ||
71 | assert_eq!(self.nth(0), EOF); | ||
72 | self.events | ||
73 | } | ||
74 | |||
75 | pub(super) fn next2(&self) -> Option<(SyntaxKind, SyntaxKind)> { | ||
76 | let c1 = self.inp.kind(self.pos); | ||
77 | let c2 = self.inp.kind(self.pos + 1); | ||
78 | if self.inp.start(self.pos + 1) == self.inp.start(self.pos) + self.inp.len(self.pos) { | ||
79 | Some((c1, c2)) | ||
80 | } else { | ||
81 | None | ||
82 | } | ||
83 | } | ||
84 | |||
85 | pub(super) fn next3(&self) -> Option<(SyntaxKind, SyntaxKind, SyntaxKind)> { | ||
86 | let c1 = self.inp.kind(self.pos); | ||
87 | let c2 = self.inp.kind(self.pos + 1); | ||
88 | let c3 = self.inp.kind(self.pos + 2); | ||
89 | if self.inp.start(self.pos + 1) == self.inp.start(self.pos) + self.inp.len(self.pos) | ||
90 | && self.inp.start(self.pos + 2) == self.inp.start(self.pos + 1) + self.inp.len(self.pos + 1){ | ||
91 | Some((c1, c2, c3)) | ||
92 | } else { | ||
93 | None | ||
94 | } | ||
95 | } | ||
96 | |||
97 | pub(super) fn nth(&self, n: u32) -> SyntaxKind { | ||
98 | let steps = self.steps.get(); | ||
99 | if steps > 10_000_000 { | ||
100 | panic!("the parser seems stuck"); | ||
101 | } | ||
102 | self.steps.set(steps + 1); | ||
103 | |||
104 | self.inp.kind(self.pos + n) | ||
105 | } | ||
106 | |||
107 | pub(super) fn at_kw(&self, t: &str) -> bool { | ||
108 | self.inp.text(self.pos) == t | ||
109 | } | ||
110 | |||
111 | pub(super) fn start(&mut self) -> u32 { | ||
112 | let pos = self.events.len() as u32; | ||
113 | self.event(Event::Start { | ||
114 | kind: TOMBSTONE, | ||
115 | forward_parent: None, | ||
116 | }); | ||
117 | pos | ||
118 | } | ||
119 | |||
120 | pub(super) fn bump(&mut self) { | ||
121 | let kind = self.nth(0); | ||
122 | if kind == EOF { | ||
123 | return; | ||
124 | } | ||
125 | self.do_bump(kind, 1); | ||
126 | } | ||
127 | |||
128 | pub(super) fn bump_remap(&mut self, kind: SyntaxKind) { | ||
129 | if self.nth(0) == EOF { | ||
130 | // TODO: panic!? | ||
131 | return; | ||
132 | } | ||
133 | self.do_bump(kind, 1); | ||
134 | } | ||
135 | |||
136 | pub(super) fn bump_compound(&mut self, kind: SyntaxKind, n: u8) { | ||
137 | self.do_bump(kind, n); | ||
138 | } | ||
139 | |||
140 | fn do_bump(&mut self, kind: SyntaxKind, n_raw_tokens: u8) { | ||
141 | self.pos += u32::from(n_raw_tokens); | ||
142 | self.event(Event::Token { | ||
143 | kind, | ||
144 | n_raw_tokens, | ||
145 | }); | ||
146 | } | ||
147 | |||
148 | pub(super) fn error(&mut self, msg: String) { | ||
149 | self.event(Event::Error { msg }) | ||
150 | } | ||
151 | |||
152 | pub(super) fn complete(&mut self, pos: u32, kind: SyntaxKind) { | ||
153 | match self.events[pos as usize] { | ||
154 | Event::Start { | ||
155 | kind: ref mut slot, .. | ||
156 | } => { | ||
157 | *slot = kind; | ||
158 | } | ||
159 | _ => unreachable!(), | ||
160 | } | ||
161 | self.event(Event::Finish); | ||
162 | } | ||
163 | |||
164 | pub(super) fn abandon(&mut self, pos: u32) { | ||
165 | let idx = pos as usize; | ||
166 | if idx == self.events.len() - 1 { | ||
167 | match self.events.pop() { | ||
168 | Some(Event::Start { | ||
169 | kind: TOMBSTONE, | ||
170 | forward_parent: None, | ||
171 | }) => (), | ||
172 | _ => unreachable!(), | ||
173 | } | ||
174 | } | ||
175 | } | ||
176 | |||
177 | pub(super) fn precede(&mut self, pos: u32) -> u32 { | ||
178 | let new_pos = self.start(); | ||
179 | match self.events[pos as usize] { | ||
180 | Event::Start { | ||
181 | ref mut forward_parent, | ||
182 | .. | ||
183 | } => { | ||
184 | *forward_parent = Some(new_pos - pos); | ||
185 | } | ||
186 | _ => unreachable!(), | ||
187 | } | ||
188 | new_pos | ||
189 | } | ||
190 | |||
191 | fn event(&mut self, event: Event) { | ||
192 | self.events.push(event) | ||
193 | } | ||
194 | } | ||