aboutsummaryrefslogtreecommitdiff
path: root/crates/tt
diff options
context:
space:
mode:
Diffstat (limited to 'crates/tt')
-rw-r--r--crates/tt/Cargo.toml16
-rw-r--r--crates/tt/src/buffer.rs185
-rw-r--r--crates/tt/src/lib.rs246
3 files changed, 447 insertions, 0 deletions
diff --git a/crates/tt/Cargo.toml b/crates/tt/Cargo.toml
new file mode 100644
index 000000000..dfcdcf03e
--- /dev/null
+++ b/crates/tt/Cargo.toml
@@ -0,0 +1,16 @@
1[package]
2name = "tt"
3version = "0.0.0"
4license = "MIT OR Apache-2.0"
5authors = ["rust-analyzer developers"]
6edition = "2018"
7
8[lib]
9doctest = false
10
11[dependencies]
12# ideally, `serde` should be enabled by `rust-analyzer`, but we enable it here
13# to reduce number of compilations
14smol_str = { version = "0.1.15", features = ["serde"] }
15
16stdx = { path = "../stdx" }
diff --git a/crates/tt/src/buffer.rs b/crates/tt/src/buffer.rs
new file mode 100644
index 000000000..02c771f70
--- /dev/null
+++ b/crates/tt/src/buffer.rs
@@ -0,0 +1,185 @@
1//! FIXME: write short doc here
2
3use crate::{Subtree, TokenTree};
4
5#[derive(Copy, Clone, Debug, Eq, PartialEq)]
6struct EntryId(usize);
7
8#[derive(Copy, Clone, Debug, Eq, PartialEq)]
9struct EntryPtr(EntryId, usize);
10
11/// Internal type which is used instead of `TokenTree` to represent a token tree
12/// within a `TokenBuffer`.
13#[derive(Debug)]
14enum Entry<'t> {
15 // Mimicking types from proc-macro.
16 Subtree(&'t TokenTree, EntryId),
17 Leaf(&'t TokenTree),
18 // End entries contain a pointer to the entry from the containing
19 // token tree, or None if this is the outermost level.
20 End(Option<EntryPtr>),
21}
22
23/// A token tree buffer
24/// The safe version of `syn` [`TokenBuffer`](https://github.com/dtolnay/syn/blob/6533607f91686545cb034d2838beea338d9d0742/src/buffer.rs#L41)
25#[derive(Debug)]
26pub struct TokenBuffer<'t> {
27 buffers: Vec<Box<[Entry<'t>]>>,
28}
29
30impl<'t> TokenBuffer<'t> {
31 pub fn new(tokens: &'t [TokenTree]) -> TokenBuffer<'t> {
32 let mut buffers = vec![];
33
34 let idx = TokenBuffer::new_inner(tokens, &mut buffers, None);
35 assert_eq!(idx, 0);
36
37 TokenBuffer { buffers }
38 }
39
40 fn new_inner(
41 tokens: &'t [TokenTree],
42 buffers: &mut Vec<Box<[Entry<'t>]>>,
43 next: Option<EntryPtr>,
44 ) -> usize {
45 // Must contain everything in tokens and then the Entry::End
46 let start_capacity = tokens.len() + 1;
47 let mut entries = Vec::with_capacity(start_capacity);
48 let mut children = vec![];
49
50 for (idx, tt) in tokens.iter().enumerate() {
51 match tt {
52 TokenTree::Leaf(_) => {
53 entries.push(Entry::Leaf(tt));
54 }
55 TokenTree::Subtree(subtree) => {
56 entries.push(Entry::End(None));
57 children.push((idx, (subtree, tt)));
58 }
59 }
60 }
61
62 entries.push(Entry::End(next));
63 let res = buffers.len();
64 buffers.push(entries.into_boxed_slice());
65
66 for (child_idx, (subtree, tt)) in children {
67 let idx = TokenBuffer::new_inner(
68 &subtree.token_trees,
69 buffers,
70 Some(EntryPtr(EntryId(res), child_idx + 1)),
71 );
72 buffers[res].as_mut()[child_idx] = Entry::Subtree(tt, EntryId(idx));
73 }
74
75 res
76 }
77
78 /// Creates a cursor referencing the first token in the buffer and able to
79 /// traverse until the end of the buffer.
80 pub fn begin(&self) -> Cursor {
81 Cursor::create(self, EntryPtr(EntryId(0), 0))
82 }
83
84 fn entry(&self, ptr: &EntryPtr) -> Option<&Entry> {
85 let id = ptr.0;
86 self.buffers[id.0].get(ptr.1)
87 }
88}
89
90/// A safe version of `Cursor` from `syn` crate https://github.com/dtolnay/syn/blob/6533607f91686545cb034d2838beea338d9d0742/src/buffer.rs#L125
91#[derive(Copy, Clone, Debug)]
92pub struct Cursor<'a> {
93 buffer: &'a TokenBuffer<'a>,
94 ptr: EntryPtr,
95}
96
97impl<'a> PartialEq for Cursor<'a> {
98 fn eq(&self, other: &Cursor) -> bool {
99 self.ptr == other.ptr && std::ptr::eq(self.buffer, other.buffer)
100 }
101}
102
103impl<'a> Eq for Cursor<'a> {}
104
105impl<'a> Cursor<'a> {
106 /// Check whether it is eof
107 pub fn eof(self) -> bool {
108 matches!(self.buffer.entry(&self.ptr), None | Some(Entry::End(None)))
109 }
110
111 /// If the cursor is pointing at the end of a subtree, returns
112 /// the parent subtree
113 pub fn end(self) -> Option<&'a Subtree> {
114 match self.entry() {
115 Some(Entry::End(Some(ptr))) => {
116 let idx = ptr.1;
117 if let Some(Entry::Subtree(TokenTree::Subtree(subtree), _)) =
118 self.buffer.entry(&EntryPtr(ptr.0, idx - 1))
119 {
120 return Some(subtree);
121 }
122
123 None
124 }
125 _ => None,
126 }
127 }
128
129 fn entry(self) -> Option<&'a Entry<'a>> {
130 self.buffer.entry(&self.ptr)
131 }
132
133 /// If the cursor is pointing at a `Subtree`, returns
134 /// a cursor into that subtree
135 pub fn subtree(self) -> Option<Cursor<'a>> {
136 match self.entry() {
137 Some(Entry::Subtree(_, entry_id)) => {
138 Some(Cursor::create(self.buffer, EntryPtr(*entry_id, 0)))
139 }
140 _ => None,
141 }
142 }
143
144 /// If the cursor is pointing at a `TokenTree`, returns it
145 pub fn token_tree(self) -> Option<&'a TokenTree> {
146 match self.entry() {
147 Some(Entry::Leaf(tt)) => Some(tt),
148 Some(Entry::Subtree(tt, _)) => Some(tt),
149 Some(Entry::End(_)) => None,
150 None => None,
151 }
152 }
153
154 fn create(buffer: &'a TokenBuffer, ptr: EntryPtr) -> Cursor<'a> {
155 Cursor { buffer, ptr }
156 }
157
158 /// Bump the cursor
159 pub fn bump(self) -> Cursor<'a> {
160 if let Some(Entry::End(exit)) = self.buffer.entry(&self.ptr) {
161 if let Some(exit) = exit {
162 Cursor::create(self.buffer, *exit)
163 } else {
164 self
165 }
166 } else {
167 Cursor::create(self.buffer, EntryPtr(self.ptr.0, self.ptr.1 + 1))
168 }
169 }
170
171 /// Bump the cursor, if it is a subtree, returns
172 /// a cursor into that subtree
173 pub fn bump_subtree(self) -> Cursor<'a> {
174 match self.entry() {
175 Some(Entry::Subtree(_, _)) => self.subtree().unwrap(),
176 _ => self.bump(),
177 }
178 }
179
180 /// Check whether it is a top level
181 pub fn is_root(&self) -> bool {
182 let entry_id = self.ptr.0;
183 entry_id.0 == 0
184 }
185}
diff --git a/crates/tt/src/lib.rs b/crates/tt/src/lib.rs
new file mode 100644
index 000000000..20c3f5eab
--- /dev/null
+++ b/crates/tt/src/lib.rs
@@ -0,0 +1,246 @@
1//! `tt` crate defines a `TokenTree` data structure: this is the interface (both
2//! input and output) of macros. It closely mirrors `proc_macro` crate's
3//! `TokenTree`.
4use std::{
5 fmt::{self, Debug},
6 panic::RefUnwindSafe,
7};
8
9use stdx::impl_from;
10
11pub use smol_str::SmolStr;
12
13/// Represents identity of the token.
14///
15/// For hygiene purposes, we need to track which expanded tokens originated from
16/// which source tokens. We do it by assigning an distinct identity to each
17/// source token and making sure that identities are preserved during macro
18/// expansion.
19#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
20pub struct TokenId(pub u32);
21
22impl TokenId {
23 pub const fn unspecified() -> TokenId {
24 TokenId(!0)
25 }
26}
27
28#[derive(Debug, Clone, PartialEq, Eq, Hash)]
29pub enum TokenTree {
30 Leaf(Leaf),
31 Subtree(Subtree),
32}
33impl_from!(Leaf, Subtree for TokenTree);
34
35impl TokenTree {
36 pub fn empty() -> Self {
37 TokenTree::Subtree(Subtree::default())
38 }
39}
40
41#[derive(Debug, Clone, PartialEq, Eq, Hash)]
42pub enum Leaf {
43 Literal(Literal),
44 Punct(Punct),
45 Ident(Ident),
46}
47impl_from!(Literal, Punct, Ident for Leaf);
48
49#[derive(Clone, PartialEq, Eq, Hash, Default)]
50pub struct Subtree {
51 pub delimiter: Option<Delimiter>,
52 pub token_trees: Vec<TokenTree>,
53}
54
55#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
56pub struct Delimiter {
57 pub id: TokenId,
58 pub kind: DelimiterKind,
59}
60
61#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
62pub enum DelimiterKind {
63 Parenthesis,
64 Brace,
65 Bracket,
66}
67
68#[derive(Debug, Clone, PartialEq, Eq, Hash)]
69pub struct Literal {
70 pub text: SmolStr,
71 pub id: TokenId,
72}
73
74#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
75pub struct Punct {
76 pub char: char,
77 pub spacing: Spacing,
78 pub id: TokenId,
79}
80
81#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
82pub enum Spacing {
83 Alone,
84 Joint,
85}
86
87#[derive(Debug, Clone, PartialEq, Eq, Hash)]
88pub struct Ident {
89 pub text: SmolStr,
90 pub id: TokenId,
91}
92
93fn print_debug_subtree(f: &mut fmt::Formatter<'_>, subtree: &Subtree, level: usize) -> fmt::Result {
94 let align = std::iter::repeat(" ").take(level).collect::<String>();
95
96 let aux = match subtree.delimiter.map(|it| (it.kind, it.id.0)) {
97 None => "$".to_string(),
98 Some((DelimiterKind::Parenthesis, id)) => format!("() {}", id),
99 Some((DelimiterKind::Brace, id)) => format!("{{}} {}", id),
100 Some((DelimiterKind::Bracket, id)) => format!("[] {}", id),
101 };
102
103 if subtree.token_trees.is_empty() {
104 write!(f, "{}SUBTREE {}", align, aux)?;
105 } else {
106 writeln!(f, "{}SUBTREE {}", align, aux)?;
107 for (idx, child) in subtree.token_trees.iter().enumerate() {
108 print_debug_token(f, child, level + 1)?;
109 if idx != subtree.token_trees.len() - 1 {
110 writeln!(f)?;
111 }
112 }
113 }
114
115 Ok(())
116}
117
118fn print_debug_token(f: &mut fmt::Formatter<'_>, tkn: &TokenTree, level: usize) -> fmt::Result {
119 let align = std::iter::repeat(" ").take(level).collect::<String>();
120
121 match tkn {
122 TokenTree::Leaf(leaf) => match leaf {
123 Leaf::Literal(lit) => write!(f, "{}LITERAL {} {}", align, lit.text, lit.id.0)?,
124 Leaf::Punct(punct) => write!(
125 f,
126 "{}PUNCH {} [{}] {}",
127 align,
128 punct.char,
129 if punct.spacing == Spacing::Alone { "alone" } else { "joint" },
130 punct.id.0
131 )?,
132 Leaf::Ident(ident) => write!(f, "{}IDENT {} {}", align, ident.text, ident.id.0)?,
133 },
134 TokenTree::Subtree(subtree) => {
135 print_debug_subtree(f, subtree, level)?;
136 }
137 }
138
139 Ok(())
140}
141
142impl Debug for Subtree {
143 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
144 print_debug_subtree(f, self, 0)
145 }
146}
147
148impl fmt::Display for TokenTree {
149 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
150 match self {
151 TokenTree::Leaf(it) => fmt::Display::fmt(it, f),
152 TokenTree::Subtree(it) => fmt::Display::fmt(it, f),
153 }
154 }
155}
156
157impl fmt::Display for Subtree {
158 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
159 let (l, r) = match self.delimiter_kind() {
160 Some(DelimiterKind::Parenthesis) => ("(", ")"),
161 Some(DelimiterKind::Brace) => ("{", "}"),
162 Some(DelimiterKind::Bracket) => ("[", "]"),
163 None => ("", ""),
164 };
165 f.write_str(l)?;
166 let mut needs_space = false;
167 for tt in self.token_trees.iter() {
168 if needs_space {
169 f.write_str(" ")?;
170 }
171 needs_space = true;
172 match tt {
173 TokenTree::Leaf(Leaf::Punct(p)) => {
174 needs_space = p.spacing == Spacing::Alone;
175 fmt::Display::fmt(p, f)?
176 }
177 tt => fmt::Display::fmt(tt, f)?,
178 }
179 }
180 f.write_str(r)?;
181 Ok(())
182 }
183}
184
185impl fmt::Display for Leaf {
186 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
187 match self {
188 Leaf::Ident(it) => fmt::Display::fmt(it, f),
189 Leaf::Literal(it) => fmt::Display::fmt(it, f),
190 Leaf::Punct(it) => fmt::Display::fmt(it, f),
191 }
192 }
193}
194
195impl fmt::Display for Ident {
196 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
197 fmt::Display::fmt(&self.text, f)
198 }
199}
200
201impl fmt::Display for Literal {
202 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
203 fmt::Display::fmt(&self.text, f)
204 }
205}
206
207impl fmt::Display for Punct {
208 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
209 fmt::Display::fmt(&self.char, f)
210 }
211}
212
213impl Subtree {
214 /// Count the number of tokens recursively
215 pub fn count(&self) -> usize {
216 let children_count = self
217 .token_trees
218 .iter()
219 .map(|c| match c {
220 TokenTree::Subtree(c) => c.count(),
221 _ => 0,
222 })
223 .sum::<usize>();
224
225 self.token_trees.len() + children_count
226 }
227
228 pub fn delimiter_kind(&self) -> Option<DelimiterKind> {
229 self.delimiter.map(|it| it.kind)
230 }
231}
232
233pub mod buffer;
234
235#[derive(Debug, PartialEq, Eq, Clone)]
236pub enum ExpansionError {
237 IOError(String),
238 JsonError(String),
239 Unknown(String),
240 ExpansionError(String),
241}
242
243pub trait TokenExpander: Debug + Send + Sync + RefUnwindSafe {
244 fn expand(&self, subtree: &Subtree, attrs: Option<&Subtree>)
245 -> Result<Subtree, ExpansionError>;
246}