From 37ef8927c373b8eadd63edc1f70055428c49290e Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Tue, 17 Sep 2019 02:06:14 +0300 Subject: split mbe expander code into two modules --- crates/ra_mbe/src/mbe_expander/matcher.rs | 215 ++++++++++++++++++++++++ crates/ra_mbe/src/mbe_expander/transcriber.rs | 227 ++++++++++++++++++++++++++ 2 files changed, 442 insertions(+) create mode 100644 crates/ra_mbe/src/mbe_expander/matcher.rs create mode 100644 crates/ra_mbe/src/mbe_expander/transcriber.rs (limited to 'crates/ra_mbe/src/mbe_expander') diff --git a/crates/ra_mbe/src/mbe_expander/matcher.rs b/crates/ra_mbe/src/mbe_expander/matcher.rs new file mode 100644 index 000000000..100a3b0e0 --- /dev/null +++ b/crates/ra_mbe/src/mbe_expander/matcher.rs @@ -0,0 +1,215 @@ +use crate::{ + mbe_expander::{Binding, Bindings, Fragment}, + tt_cursor::TtCursor, + ExpandError, +}; + +use ra_parser::FragmentKind::*; +use ra_syntax::SmolStr; + +impl Bindings { + fn push_optional(&mut self, name: &SmolStr) { + // FIXME: Do we have a better way to represent an empty token ? + // Insert an empty subtree for empty token + let tt = tt::Subtree { delimiter: tt::Delimiter::None, token_trees: vec![] }.into(); + self.inner.insert(name.clone(), Binding::Fragment(Fragment::Tokens(tt))); + } + + fn push_empty(&mut self, name: &SmolStr) { + self.inner.insert(name.clone(), Binding::Empty); + } + + fn push_nested(&mut self, idx: usize, nested: Bindings) -> Result<(), ExpandError> { + for (key, value) in nested.inner { + if !self.inner.contains_key(&key) { + self.inner.insert(key.clone(), Binding::Nested(Vec::new())); + } + match self.inner.get_mut(&key) { + Some(Binding::Nested(it)) => { + // insert empty nested bindings before this one + while it.len() < idx { + it.push(Binding::Nested(vec![])); + } + it.push(value); + } + _ => { + return Err(ExpandError::BindingError(format!( + "could not find binding `{}`", + key + ))); + } + } + } + Ok(()) + } + + fn merge(&mut self, nested: Bindings) { + self.inner.extend(nested.inner); + } +} + +pub(super) fn match_lhs( + pattern: &crate::Subtree, + input: &mut TtCursor, +) -> Result { + let mut res = Bindings::default(); + for pat in pattern.token_trees.iter() { + match pat { + crate::TokenTree::Leaf(leaf) => match leaf { + crate::Leaf::Var(crate::Var { text, kind }) => { + let kind = kind.as_ref().ok_or(ExpandError::UnexpectedToken)?; + match match_meta_var(kind.as_str(), input)? { + Some(fragment) => { + res.inner.insert(text.clone(), Binding::Fragment(fragment)); + } + None => res.push_optional(text), + } + } + crate::Leaf::Punct(punct) => { + if !input.eat_punct().map(|p| p.char == punct.char).unwrap_or(false) { + return Err(ExpandError::UnexpectedToken); + } + } + crate::Leaf::Ident(ident) => { + if input.eat_ident().map(|i| &i.text) != Some(&ident.text) { + return Err(ExpandError::UnexpectedToken); + } + } + crate::Leaf::Literal(literal) => { + if input.eat_literal().map(|i| &i.text) != Some(&literal.text) { + return Err(ExpandError::UnexpectedToken); + } + } + }, + crate::TokenTree::Repeat(crate::Repeat { subtree, kind, separator }) => { + // Dirty hack to make macro-expansion terminate. + // This should be replaced by a propper macro-by-example implementation + let mut limit = 65536; + let mut counter = 0; + + let mut memento = input.save(); + + loop { + match match_lhs(subtree, input) { + Ok(nested) => { + limit -= 1; + if limit == 0 { + log::warn!("match_lhs excced in repeat pattern exceed limit => {:#?}\n{:#?}\n{:#?}\n{:#?}", subtree, input, kind, separator); + break; + } + + memento = input.save(); + res.push_nested(counter, nested)?; + counter += 1; + if counter == 1 { + if let crate::RepeatKind::ZeroOrOne = kind { + break; + } + } + + if let Some(separator) = separator { + if !input + .eat_seperator() + .map(|sep| sep == *separator) + .unwrap_or(false) + { + input.rollback(memento); + break; + } + } + } + Err(_) => { + input.rollback(memento); + break; + } + } + } + + match kind { + crate::RepeatKind::OneOrMore if counter == 0 => { + return Err(ExpandError::UnexpectedToken); + } + _ if counter == 0 => { + // Collect all empty variables in subtrees + collect_vars(subtree).iter().for_each(|s| res.push_empty(s)); + } + _ => {} + } + } + crate::TokenTree::Subtree(subtree) => { + let input_subtree = + input.eat_subtree().map_err(|_| ExpandError::UnexpectedToken)?; + if subtree.delimiter != input_subtree.delimiter { + return Err(ExpandError::UnexpectedToken); + } + + let mut input = TtCursor::new(input_subtree); + let bindings = match_lhs(&subtree, &mut input)?; + if !input.is_eof() { + return Err(ExpandError::UnexpectedToken); + } + + res.merge(bindings); + } + } + } + Ok(res) +} + +fn match_meta_var(kind: &str, input: &mut TtCursor) -> Result, ExpandError> { + let fragment = match kind { + "path" => Path, + "expr" => Expr, + "ty" => Type, + "pat" => Pattern, + "stmt" => Statement, + "block" => Block, + "meta" => MetaItem, + "item" => Item, + _ => { + let tt = match kind { + "ident" => { + let ident = input.eat_ident().ok_or(ExpandError::UnexpectedToken)?.clone(); + tt::Leaf::from(ident).into() + } + "tt" => input.eat().ok_or(ExpandError::UnexpectedToken)?.clone(), + "lifetime" => input.eat_lifetime().ok_or(ExpandError::UnexpectedToken)?.clone(), + "literal" => { + let literal = input.eat_literal().ok_or(ExpandError::UnexpectedToken)?.clone(); + tt::Leaf::from(literal).into() + } + // `vis` is optional + "vis" => match input.try_eat_vis() { + Some(vis) => vis, + None => return Ok(None), + }, + _ => return Err(ExpandError::UnexpectedToken), + }; + return Ok(Some(Fragment::Tokens(tt))); + } + }; + let tt = input.eat_fragment(fragment).ok_or(ExpandError::UnexpectedToken)?; + let fragment = if kind == "expr" { Fragment::Ast(tt) } else { Fragment::Tokens(tt) }; + Ok(Some(fragment)) +} + +fn collect_vars(subtree: &crate::Subtree) -> Vec { + let mut res = Vec::new(); + + for tkn in subtree.token_trees.iter() { + match tkn { + crate::TokenTree::Leaf(crate::Leaf::Var(crate::Var { text, .. })) => { + res.push(text.clone()); + } + crate::TokenTree::Subtree(subtree) => { + res.extend(collect_vars(subtree)); + } + crate::TokenTree::Repeat(crate::Repeat { subtree, .. }) => { + res.extend(collect_vars(subtree)); + } + _ => {} + } + } + + res +} diff --git a/crates/ra_mbe/src/mbe_expander/transcriber.rs b/crates/ra_mbe/src/mbe_expander/transcriber.rs new file mode 100644 index 000000000..a3df1b7de --- /dev/null +++ b/crates/ra_mbe/src/mbe_expander/transcriber.rs @@ -0,0 +1,227 @@ +use ra_syntax::SmolStr; + +use crate::{ + mbe_expander::{Binding, Bindings, Fragment}, + ExpandError, +}; + +impl Bindings { + fn contains(&self, name: &SmolStr) -> bool { + self.inner.contains_key(name) + } + + fn get(&self, name: &SmolStr, nesting: &[usize]) -> Result<&Fragment, ExpandError> { + let mut b = self.inner.get(name).ok_or_else(|| { + ExpandError::BindingError(format!("could not find binding `{}`", name)) + })?; + for &idx in nesting.iter() { + b = match b { + Binding::Fragment(_) => break, + Binding::Nested(bs) => bs.get(idx).ok_or_else(|| { + ExpandError::BindingError(format!("could not find nested binding `{}`", name)) + })?, + Binding::Empty => { + return Err(ExpandError::BindingError(format!( + "could not find empty binding `{}`", + name + ))) + } + }; + } + match b { + Binding::Fragment(it) => Ok(it), + Binding::Nested(_) => Err(ExpandError::BindingError(format!( + "expected simple binding, found nested binding `{}`", + name + ))), + Binding::Empty => Err(ExpandError::BindingError(format!( + "expected simple binding, found empty binding `{}`", + name + ))), + } + } +} + +pub(super) fn transcribe( + bindings: &Bindings, + template: &crate::Subtree, +) -> Result { + let mut ctx = ExpandCtx { bindings: &bindings, nesting: Vec::new(), var_expanded: false }; + expand_subtree(template, &mut ctx) +} + +#[derive(Debug)] +struct ExpandCtx<'a> { + bindings: &'a Bindings, + nesting: Vec, + var_expanded: bool, +} + +fn expand_subtree( + template: &crate::Subtree, + ctx: &mut ExpandCtx, +) -> Result { + let mut buf: Vec = Vec::new(); + for tt in template.token_trees.iter() { + let tt = expand_tt(tt, ctx)?; + push_fragment(&mut buf, tt); + } + + Ok(tt::Subtree { delimiter: template.delimiter, token_trees: buf }) +} + +fn expand_tt(template: &crate::TokenTree, ctx: &mut ExpandCtx) -> Result { + let res: tt::TokenTree = match template { + crate::TokenTree::Subtree(subtree) => expand_subtree(subtree, ctx)?.into(), + crate::TokenTree::Repeat(repeat) => { + let mut buf: Vec = Vec::new(); + ctx.nesting.push(0); + // Dirty hack to make macro-expansion terminate. + // This should be replaced by a propper macro-by-example implementation + let mut limit = 65536; + let mut has_seps = 0; + let mut counter = 0; + + // We store the old var expanded value, and restore it later + // It is because before this `$repeat`, + // it is possible some variables already expanad in the same subtree + // + // `some_var_expanded` keep check if the deeper subtree has expanded variables + let mut some_var_expanded = false; + let old_var_expanded = ctx.var_expanded; + ctx.var_expanded = false; + + while let Ok(t) = expand_subtree(&repeat.subtree, ctx) { + // if no var expanded in the child, we count it as a fail + if !ctx.var_expanded { + break; + } + + // Reset `ctx.var_expandeded` to see if there is other expanded variable + // in the next matching + some_var_expanded = true; + ctx.var_expanded = false; + + counter += 1; + limit -= 1; + if limit == 0 { + log::warn!( + "expand_tt excced in repeat pattern exceed limit => {:#?}\n{:#?}", + template, + ctx + ); + break; + } + + let idx = ctx.nesting.pop().unwrap(); + ctx.nesting.push(idx + 1); + push_subtree(&mut buf, t); + + if let Some(ref sep) = repeat.separator { + match sep { + crate::Separator::Ident(ident) => { + has_seps = 1; + buf.push(tt::Leaf::from(ident.clone()).into()); + } + crate::Separator::Literal(lit) => { + has_seps = 1; + buf.push(tt::Leaf::from(lit.clone()).into()); + } + + crate::Separator::Puncts(puncts) => { + has_seps = puncts.len(); + for punct in puncts { + buf.push(tt::Leaf::from(*punct).into()); + } + } + } + } + + if let crate::RepeatKind::ZeroOrOne = repeat.kind { + break; + } + } + + // Restore the `var_expanded` by combining old one and the new one + ctx.var_expanded = some_var_expanded || old_var_expanded; + + ctx.nesting.pop().unwrap(); + for _ in 0..has_seps { + buf.pop(); + } + + if crate::RepeatKind::OneOrMore == repeat.kind && counter == 0 { + return Err(ExpandError::UnexpectedToken); + } + + // Check if it is a single token subtree without any delimiter + // e.g {Delimiter:None> ['>'] /Delimiter:None>} + tt::Subtree { delimiter: tt::Delimiter::None, token_trees: buf }.into() + } + crate::TokenTree::Leaf(leaf) => match leaf { + crate::Leaf::Ident(ident) => tt::Leaf::from(tt::Ident { + text: ident.text.clone(), + id: tt::TokenId::unspecified(), + }) + .into(), + crate::Leaf::Punct(punct) => tt::Leaf::from(*punct).into(), + crate::Leaf::Var(v) => { + if v.text == "crate" { + // FIXME: Properly handle $crate token + tt::Leaf::from(tt::Ident { + text: "$crate".into(), + id: tt::TokenId::unspecified(), + }) + .into() + } else if !ctx.bindings.contains(&v.text) { + // Note that it is possible to have a `$var` inside a macro which is not bound. + // For example: + // ``` + // macro_rules! foo { + // ($a:ident, $b:ident, $c:tt) => { + // macro_rules! bar { + // ($bi:ident) => { + // fn $bi() -> u8 {$c} + // } + // } + // } + // ``` + // We just treat it a normal tokens + tt::Subtree { + delimiter: tt::Delimiter::None, + token_trees: vec![ + tt::Leaf::from(tt::Punct { char: '$', spacing: tt::Spacing::Alone }) + .into(), + tt::Leaf::from(tt::Ident { + text: v.text.clone(), + id: tt::TokenId::unspecified(), + }) + .into(), + ], + } + .into() + } else { + let fragment = ctx.bindings.get(&v.text, &ctx.nesting)?.clone(); + ctx.var_expanded = true; + return Ok(fragment); + } + } + crate::Leaf::Literal(l) => tt::Leaf::from(tt::Literal { text: l.text.clone() }).into(), + }, + }; + Ok(Fragment::Tokens(res)) +} + +fn push_fragment(buf: &mut Vec, fragment: Fragment) { + match fragment { + Fragment::Tokens(tt::TokenTree::Subtree(tt)) => push_subtree(buf, tt), + Fragment::Tokens(tt) | Fragment::Ast(tt) => buf.push(tt), + } +} + +fn push_subtree(buf: &mut Vec, tt: tt::Subtree) { + match tt.delimiter { + tt::Delimiter::None => buf.extend(tt.token_trees), + _ => buf.push(tt.into()), + } +} -- cgit v1.2.3