Merge #3580

3580: More error-resilient MBE expansion r=matklad a=flodiebold

This is the beginning of an attempt to make macro-by-example expansion more resilient, so that we still get an expansion even if no rule exactly matches, with the goal to make completion work better in macro calls.

 The general idea is to make everything return `(T, Option<ExpandError>)` instead of `Result<T, ExpandError>`; and then to try each macro arm in turn, and somehow choose the 'best' matching rule if none matches without errors. Finding that 'best' match isn't done yet; I'm currently counting how many tokens were consumed from the args before an error, but it also needs to take into account whether there were further patterns that had nothing to match.

I'll continue this later, but I'm interested whether you think this is the right path, @matklad & @edwin0cheng.

Co-authored-by: Florian Diebold <[email protected]>
Co-authored-by: Florian Diebold <[email protected]>

2 files changed, 176 insertions, 105 deletions

diff --git a/crates/ra_mbe/src/mbe_expander/matcher.rs b/crates/ra_mbe/src/mbe_expander/matcher.rs
index 49c53183a..2579382da 100644
--- a/crates/ra_mbe/src/mbe_expander/matcher.rs
+++ b/crates/ra_mbe/src/mbe_expander/matcher.rs
@@ -8,6 +8,7 @@ use crate::{
     ExpandError,
 };
 
+use super::ExpandResult;
 use ra_parser::{FragmentKind::*, TreeSink};
 use ra_syntax::{SmolStr, SyntaxKind};
 use tt::buffer::{Cursor, TokenBuffer};
@@ -58,36 +59,61 @@ macro_rules! err {
     };
 }
 
-macro_rules! bail {
-    ($($tt:tt)*) => {
-        return Err(err!($($tt)*))
-    };
+#[derive(Debug, Default)]
+pub(super) struct Match {
+    pub bindings: Bindings,
+    /// We currently just keep the first error and count the rest to compare matches.
+    pub err: Option<ExpandError>,
+    pub err_count: usize,
+    /// How many top-level token trees were left to match.
+    pub unmatched_tts: usize,
 }
 
-pub(super) fn match_(pattern: &tt::Subtree, src: &tt::Subtree) -> Result<Bindings, ExpandError> {
+impl Match {
+    pub fn add_err(&mut self, err: ExpandError) {
+        let prev_err = self.err.take();
+        self.err = prev_err.or(Some(err));
+        self.err_count += 1;
+    }
+}
+
+// General note: These functions have two channels to return errors, a `Result`
+// return value and the `&mut Match`. The returned Result is for pattern parsing
+// errors; if a branch of the macro definition doesn't parse, it doesn't make
+// sense to try using it. Matching errors are added to the `Match`. It might
+// make sense to make pattern parsing a separate step?
+
+pub(super) fn match_(pattern: &tt::Subtree, src: &tt::Subtree) -> Result<Match, ExpandError> {
     assert!(pattern.delimiter == None);
 
-    let mut res = Bindings::default();
+    let mut res = Match::default();
     let mut src = TtIter::new(src);
 
     match_subtree(&mut res, pattern, &mut src)?;
 
     if src.len() > 0 {
-        bail!("leftover tokens");
+        res.unmatched_tts += src.len();
+        res.add_err(err!("leftover tokens"));
     }
 
     Ok(res)
 }
 
 fn match_subtree(
-    bindings: &mut Bindings,
+    res: &mut Match,
     pattern: &tt::Subtree,
     src: &mut TtIter,
 ) -> Result<(), ExpandError> {
     for op in parse_pattern(pattern) {
         match op? {
             Op::TokenTree(tt::TokenTree::Leaf(lhs)) => {
-                let rhs = src.expect_leaf().map_err(|()| err!("expected leaf: `{}`", lhs))?;
+                let rhs = match src.expect_leaf() {
+                    Ok(l) => l,
+                    Err(()) => {
+                        res.add_err(err!("expected leaf: `{}`", lhs));
+                        continue;
+                    }
+                };
                 match (lhs, rhs) {
                     (
                         tt::Leaf::Punct(tt::Punct { char: lhs, .. }),
@@ -101,31 +127,51 @@ fn match_subtree(
                         tt::Leaf::Literal(tt::Literal { text: lhs, .. }),
                         tt::Leaf::Literal(tt::Literal { text: rhs, .. }),
                     ) if lhs == rhs => (),
-                    _ => return Err(ExpandError::UnexpectedToken),
+                    _ => {
+                        res.add_err(ExpandError::UnexpectedToken);
+                    }
                 }
             }
             Op::TokenTree(tt::TokenTree::Subtree(lhs)) => {
-                let rhs = src.expect_subtree().map_err(|()| err!("expected subtree"))?;
+                let rhs = match src.expect_subtree() {
+                    Ok(s) => s,
+                    Err(()) => {
+                        res.add_err(err!("expected subtree"));
+                        continue;
+                    }
+                };
                 if lhs.delimiter_kind() != rhs.delimiter_kind() {
-                    bail!("mismatched delimiter")
+                    res.add_err(err!("mismatched delimiter"));
+                    continue;
                 }
                 let mut src = TtIter::new(rhs);
-                match_subtree(bindings, lhs, &mut src)?;
+                match_subtree(res, lhs, &mut src)?;
                 if src.len() > 0 {
-                    bail!("leftover tokens");
+                    res.add_err(err!("leftover tokens"));
                 }
             }
             Op::Var { name, kind } => {
-                let kind = kind.as_ref().ok_or(ExpandError::UnexpectedToken)?;
-                match match_meta_var(kind.as_str(), src)? {
+                let kind = match kind {
+                    Some(k) => k,
+                    None => {
+                        res.add_err(ExpandError::UnexpectedToken);
+                        continue;
+                    }
+                };
+                let ExpandResult(matched, match_err) = match_meta_var(kind.as_str(), src);
+                match matched {
                     Some(fragment) => {
-                        bindings.inner.insert(name.clone(), Binding::Fragment(fragment));
+                        res.bindings.inner.insert(name.clone(), Binding::Fragment(fragment));
                     }
-                    None => bindings.push_optional(name),
+                    None if match_err.is_none() => res.bindings.push_optional(name),
+                    _ => {}
+                }
+                if let Some(err) = match_err {
+                    res.add_err(err);
                 }
             }
             Op::Repeat { subtree, kind, separator } => {
-                match_repeat(bindings, subtree, kind, separator, src)?
+                match_repeat(res, subtree, kind, separator, src)?;
             }
         }
     }
@@ -221,7 +267,7 @@ impl<'a> TtIter<'a> {
     pub(crate) fn expect_fragment(
         &mut self,
         fragment_kind: ra_parser::FragmentKind,
-    ) -> Result<tt::TokenTree, ()> {
+    ) -> ExpandResult<Option<tt::TokenTree>> {
         pub(crate) struct OffsetTokenSink<'a> {
             pub(crate) cursor: Cursor<'a>,
             pub(crate) error: bool,
@@ -246,45 +292,51 @@ impl<'a> TtIter<'a> {
 
         ra_parser::parse_fragment(&mut src, &mut sink, fragment_kind);
 
+        let mut err = None;
         if !sink.cursor.is_root() || sink.error {
-            // FIXME better recovery in this case would help completion inside macros immensely
-            return Err(());
+            err = Some(err!("expected {:?}", fragment_kind));
         }
 
         let mut curr = buffer.begin();
         let mut res = vec![];
 
-        while curr != sink.cursor {
-            if let Some(token) = curr.token_tree() {
-                res.push(token);
+        if sink.cursor.is_root() {
+            while curr != sink.cursor {
+                if let Some(token) = curr.token_tree() {
+                    res.push(token);
+                }
+                curr = curr.bump();
             }
-            curr = curr.bump();
         }
         self.inner = self.inner.as_slice()[res.len()..].iter();
-        match res.len() {
-            0 => Err(()),
-            1 => Ok(res[0].clone()),
-            _ => Ok(tt::TokenTree::Subtree(tt::Subtree {
+        if res.len() == 0 && err.is_none() {
+            err = Some(err!("no tokens consumed"));
+        }
+        let res = match res.len() {
+            1 => Some(res[0].clone()),
+            0 => None,
+            _ => Some(tt::TokenTree::Subtree(tt::Subtree {
                 delimiter: None,
                 token_trees: res.into_iter().cloned().collect(),
             })),
-        }
+        };
+        ExpandResult(res, err)
     }
 
     pub(crate) fn eat_vis(&mut self) -> Option<tt::TokenTree> {
         let mut fork = self.clone();
         match fork.expect_fragment(Visibility) {
-            Ok(tt) => {
+            ExpandResult(tt, None) => {
                 *self = fork;
-                Some(tt)
+                tt
             }
-            Err(()) => None,
+            ExpandResult(_, Some(_)) => None,
         }
     }
 }
 
 pub(super) fn match_repeat(
-    bindings: &mut Bindings,
+    res: &mut Match,
     pattern: &tt::Subtree,
     kind: RepeatKind,
     separator: Option<Separator>,
@@ -304,36 +356,46 @@ pub(super) fn match_repeat(
             }
         }
 
-        let mut nested = Bindings::default();
-        match match_subtree(&mut nested, pattern, &mut fork) {
-            Ok(()) => {
-                limit -= 1;
-                if limit == 0 {
-                    log::warn!("match_lhs excced in repeat pattern exceed limit => {:#?}\n{:#?}\n{:#?}\n{:#?}", pattern, src, kind, separator);
-                    break;
-                }
-                *src = fork;
+        let mut nested = Match::default();
+        match_subtree(&mut nested, pattern, &mut fork)?;
+        if nested.err.is_none() {
+            limit -= 1;
+            if limit == 0 {
+                log::warn!(
+                    "match_lhs exceeded repeat pattern limit => {:#?}\n{:#?}\n{:#?}\n{:#?}",
+                    pattern,
+                    src,
+                    kind,
+                    separator
+                );
+                break;
+            }
+            *src = fork;
 
-                bindings.push_nested(counter, nested)?;
-                counter += 1;
-                if counter == 1 {
-                    if let RepeatKind::ZeroOrOne = kind {
-                        break;
-                    }
+            if let Err(err) = res.bindings.push_nested(counter, nested.bindings) {
+                res.add_err(err);
+            }
+            counter += 1;
+            if counter == 1 {
+                if let RepeatKind::ZeroOrOne = kind {
+                    break;
                 }
             }
-            Err(_) => break,
+        } else {
+            break;
         }
     }
 
     match (kind, counter) {
-        (RepeatKind::OneOrMore, 0) => return Err(ExpandError::UnexpectedToken),
+        (RepeatKind::OneOrMore, 0) => {
+            res.add_err(ExpandError::UnexpectedToken);
+        }
         (_, 0) => {
             // Collect all empty variables in subtrees
             let mut vars = Vec::new();
             collect_vars(&mut vars, pattern)?;
             for var in vars {
-                bindings.push_empty(&var)
+                res.bindings.push_empty(&var)
             }
         }
         _ => (),
@@ -341,7 +403,7 @@ pub(super) fn match_repeat(
     Ok(())
 }
 
-fn match_meta_var(kind: &str, input: &mut TtIter) -> Result<Option<Fragment>, ExpandError> {
+fn match_meta_var(kind: &str, input: &mut TtIter) -> ExpandResult<Option<Fragment>> {
     let fragment = match kind {
         "path" => Path,
         "expr" => Expr,
@@ -352,34 +414,32 @@ fn match_meta_var(kind: &str, input: &mut TtIter) -> Result<Option<Fragment>, Ex
         "meta" => MetaItem,
         "item" => Item,
         _ => {
-            let tt = match kind {
-                "ident" => {
-                    let ident = input.expect_ident().map_err(|()| err!("expected ident"))?.clone();
-                    tt::Leaf::from(ident).into()
-                }
-                "tt" => input.expect_tt().map_err(|()| err!())?.clone(),
-                "lifetime" => {
-                    let ident = input.expect_lifetime().map_err(|()| err!())?;
-                    tt::Leaf::Ident(ident.clone()).into()
-                }
-                "literal" => {
-                    let literal = input.expect_literal().map_err(|()| err!())?.clone();
-                    tt::Leaf::from(literal).into()
-                }
+            let tt_result = match kind {
+                "ident" => input
+                    .expect_ident()
+                    .map(|ident| Some(tt::Leaf::from(ident.clone()).into()))
+                    .map_err(|()| err!("expected ident")),
+                "tt" => input.expect_tt().map(Some).map_err(|()| err!()),
+                "lifetime" => input
+                    .expect_lifetime()
+                    .map(|ident| Some(tt::Leaf::Ident(ident.clone()).into()))
+                    .map_err(|()| err!("expected lifetime")),
+                "literal" => input
+                    .expect_literal()
+                    .map(|literal| Some(tt::Leaf::from(literal.clone()).into()))
+                    .map_err(|()| err!()),
                 // `vis` is optional
                 "vis" => match input.eat_vis() {
-                    Some(vis) => vis,
-                    None => return Ok(None),
+                    Some(vis) => Ok(Some(vis)),
+                    None => Ok(None),
                 },
-                _ => return Err(ExpandError::UnexpectedToken),
+                _ => Err(ExpandError::UnexpectedToken),
             };
-            return Ok(Some(Fragment::Tokens(tt)));
+            return tt_result.map(|it| it.map(Fragment::Tokens)).into();
         }
     };
-    let tt =
-        input.expect_fragment(fragment).map_err(|()| err!("fragment did not parse as {}", kind))?;
-    let fragment = if kind == "expr" { Fragment::Ast(tt) } else { Fragment::Tokens(tt) };
-    Ok(Some(fragment))
+    let result = input.expect_fragment(fragment);
+    result.map(|tt| if kind == "expr" { tt.map(Fragment::Ast) } else { tt.map(Fragment::Tokens) })
 }
 
 fn collect_vars(buf: &mut Vec<SmolStr>, pattern: &tt::Subtree) -> Result<(), ExpandError> {
diff --git a/crates/ra_mbe/src/mbe_expander/transcriber.rs b/crates/ra_mbe/src/mbe_expander/transcriber.rs
index 7662020f3..4b173edd3 100644
--- a/crates/ra_mbe/src/mbe_expander/transcriber.rs
+++ b/crates/ra_mbe/src/mbe_expander/transcriber.rs
@@ -3,6 +3,7 @@
 
 use ra_syntax::SmolStr;
 
+use super::ExpandResult;
 use crate::{
     mbe_expander::{Binding, Bindings, Fragment},
     parser::{parse_template, Op, RepeatKind, Separator},
@@ -49,10 +50,7 @@ impl Bindings {
     }
 }
 
-pub(super) fn transcribe(
-    template: &tt::Subtree,
-    bindings: &Bindings,
-) -> Result<tt::Subtree, ExpandError> {
+pub(super) fn transcribe(template: &tt::Subtree, bindings: &Bindings) -> ExpandResult<tt::Subtree> {
     assert!(template.delimiter == None);
     let mut ctx = ExpandCtx { bindings: &bindings, nesting: Vec::new() };
     expand_subtree(&mut ctx, template)
@@ -75,35 +73,46 @@ struct ExpandCtx<'a> {
     nesting: Vec<NestingState>,
 }
 
-fn expand_subtree(ctx: &mut ExpandCtx, template: &tt::Subtree) -> Result<tt::Subtree, ExpandError> {
+fn expand_subtree(ctx: &mut ExpandCtx, template: &tt::Subtree) -> ExpandResult<tt::Subtree> {
     let mut buf: Vec<tt::TokenTree> = Vec::new();
+    let mut err = None;
     for op in parse_template(template) {
-        match op? {
+        let op = match op {
+            Ok(op) => op,
+            Err(e) => {
+                err = Some(e);
+                break;
+            }
+        };
+        match op {
             Op::TokenTree(tt @ tt::TokenTree::Leaf(..)) => buf.push(tt.clone()),
             Op::TokenTree(tt::TokenTree::Subtree(tt)) => {
-                let tt = expand_subtree(ctx, tt)?;
+                let ExpandResult(tt, e) = expand_subtree(ctx, tt);
+                err = err.or(e);
                 buf.push(tt.into());
             }
             Op::Var { name, kind: _ } => {
-                let fragment = expand_var(ctx, name)?;
+                let ExpandResult(fragment, e) = expand_var(ctx, name);
+                err = err.or(e);
                 push_fragment(&mut buf, fragment);
             }
             Op::Repeat { subtree, kind, separator } => {
-                let fragment = expand_repeat(ctx, subtree, kind, separator)?;
+                let ExpandResult(fragment, e) = expand_repeat(ctx, subtree, kind, separator);
+                err = err.or(e);
                 push_fragment(&mut buf, fragment)
             }
         }
     }
-    Ok(tt::Subtree { delimiter: template.delimiter, token_trees: buf })
+    ExpandResult(tt::Subtree { delimiter: template.delimiter, token_trees: buf }, err)
 }
 
-fn expand_var(ctx: &mut ExpandCtx, v: &SmolStr) -> Result<Fragment, ExpandError> {
-    let res = if v == "crate" {
+fn expand_var(ctx: &mut ExpandCtx, v: &SmolStr) -> ExpandResult<Fragment> {
+    if v == "crate" {
         // We simply produce identifier `$crate` here. And it will be resolved when lowering ast to Path.
         let tt =
             tt::Leaf::from(tt::Ident { text: "$crate".into(), id: tt::TokenId::unspecified() })
                 .into();
-        Fragment::Tokens(tt)
+        ExpandResult::ok(Fragment::Tokens(tt))
     } else if !ctx.bindings.contains(v) {
         // Note that it is possible to have a `$var` inside a macro which is not bound.
         // For example:
@@ -132,11 +141,13 @@ fn expand_var(ctx: &mut ExpandCtx, v: &SmolStr) -> Result<Fragment, ExpandError>
             ],
         }
         .into();
-        Fragment::Tokens(tt)
+        ExpandResult::ok(Fragment::Tokens(tt))
     } else {
-        ctx.bindings.get(&v, &mut ctx.nesting)?.clone()
-    };
-    Ok(res)
+        ctx.bindings.get(&v, &mut ctx.nesting).map_or_else(
+            |e| ExpandResult(Fragment::Tokens(tt::TokenTree::empty()), Some(e)),
+            |b| ExpandResult::ok(b.clone()),
+        )
+    }
 }
 
 fn expand_repeat(
@@ -144,17 +155,17 @@ fn expand_repeat(
     template: &tt::Subtree,
     kind: RepeatKind,
     separator: Option<Separator>,
-) -> Result<Fragment, ExpandError> {
+) -> ExpandResult<Fragment> {
     let mut buf: Vec<tt::TokenTree> = Vec::new();
     ctx.nesting.push(NestingState { idx: 0, at_end: false, hit: false });
     // Dirty hack to make macro-expansion terminate.
-    // This should be replaced by a propper macro-by-example implementation
+    // This should be replaced by a proper macro-by-example implementation
     let limit = 65536;
     let mut has_seps = 0;
     let mut counter = 0;
 
     loop {
-        let res = expand_subtree(ctx, template);
+        let ExpandResult(mut t, e) = expand_subtree(ctx, template);
         let nesting_state = ctx.nesting.last_mut().unwrap();
         if nesting_state.at_end || !nesting_state.hit {
             break;
@@ -172,10 +183,10 @@ fn expand_repeat(
             break;
         }
 
-        let mut t = match res {
-            Ok(t) => t,
-            Err(_) => continue,
-        };
+        if e.is_some() {
+            continue;
+        }
+
         t.delimiter = None;
         push_subtree(&mut buf, t);
 
@@ -209,14 +220,14 @@ fn expand_repeat(
         buf.pop();
     }
 
-    if RepeatKind::OneOrMore == kind && counter == 0 {
-        return Err(ExpandError::UnexpectedToken);
-    }
-
     // Check if it is a single token subtree without any delimiter
     // e.g {Delimiter:None> ['>'] /Delimiter:None>}
     let tt = tt::Subtree { delimiter: None, token_trees: buf }.into();
-    Ok(Fragment::Tokens(tt))
+
+    if RepeatKind::OneOrMore == kind && counter == 0 {
+        return ExpandResult(Fragment::Tokens(tt), Some(ExpandError::UnexpectedToken));
+    }
+    ExpandResult::ok(Fragment::Tokens(tt))
 }
 
 fn push_fragment(buf: &mut Vec<tt::TokenTree>, fragment: Fragment) {