From b973158aeb337041d4e1434cf5d8c609a0b02bef Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Fri, 13 Mar 2020 13:03:31 +0100 Subject: Make MBE expansion more resilient (WIP) --- crates/ra_mbe/src/mbe_expander.rs | 29 ++++++++++++++++++++--------- 1 file changed, 20 insertions(+), 9 deletions(-) (limited to 'crates/ra_mbe/src/mbe_expander.rs') diff --git a/crates/ra_mbe/src/mbe_expander.rs b/crates/ra_mbe/src/mbe_expander.rs index b455b7321..da3952428 100644 --- a/crates/ra_mbe/src/mbe_expander.rs +++ b/crates/ra_mbe/src/mbe_expander.rs @@ -8,19 +8,30 @@ mod transcriber; use ra_syntax::SmolStr; use rustc_hash::FxHashMap; -use crate::ExpandError; +use crate::{ExpandResult, ExpandError}; pub(crate) fn expand( rules: &crate::MacroRules, input: &tt::Subtree, -) -> Result { - rules.rules.iter().find_map(|it| expand_rule(it, input).ok()).ok_or(ExpandError::NoMatchingRule) +) -> ExpandResult { + let (mut result, mut err) = (tt::Subtree::default(), Some(ExpandError::NoMatchingRule)); + for rule in &rules.rules { + let (res, e) = expand_rule(rule, input); + if e.is_none() { + // if we find a rule that applies without errors, we're done + return (res, None); + } + // TODO decide which result is better + result = res; + err = e; + } + (result, err) } -fn expand_rule(rule: &crate::Rule, input: &tt::Subtree) -> Result { - let bindings = matcher::match_(&rule.lhs, input)?; - let res = transcriber::transcribe(&rule.rhs, &bindings)?; - Ok(res) +fn expand_rule(rule: &crate::Rule, input: &tt::Subtree) -> ExpandResult { + let (bindings, bindings_err) = dbg!(matcher::match_(&rule.lhs, input)); + let (res, transcribe_err) = dbg!(transcriber::transcribe(&rule.rhs, &bindings)); + (res, bindings_err.or(transcribe_err)) } /// The actual algorithm for expansion is not too hard, but is pretty tricky. @@ -111,7 +122,7 @@ mod tests { } fn assert_err(macro_body: &str, invocation: &str, err: ExpandError) { - assert_eq!(expand_first(&create_rules(&format_macro(macro_body)), invocation), Err(err)); + assert_eq!(expand_first(&create_rules(&format_macro(macro_body)), invocation).1, Some(err)); } fn format_macro(macro_body: &str) -> String { @@ -138,7 +149,7 @@ mod tests { fn expand_first( rules: &crate::MacroRules, invocation: &str, - ) -> Result { + ) -> ExpandResult { let source_file = ast::SourceFile::parse(invocation).ok().unwrap(); let macro_invocation = source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap(); -- cgit v1.2.3 From 6305d094ac61ed6e437537b93f4e587b415678c9 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Fri, 13 Mar 2020 15:18:17 +0100 Subject: Attempt to implement ranking of rules when none matches perfectly (wip) --- crates/ra_mbe/src/mbe_expander.rs | 19 +++++++++++-------- 1 file changed, 11 insertions(+), 8 deletions(-) (limited to 'crates/ra_mbe/src/mbe_expander.rs') diff --git a/crates/ra_mbe/src/mbe_expander.rs b/crates/ra_mbe/src/mbe_expander.rs index da3952428..5083d5410 100644 --- a/crates/ra_mbe/src/mbe_expander.rs +++ b/crates/ra_mbe/src/mbe_expander.rs @@ -14,24 +14,27 @@ pub(crate) fn expand( rules: &crate::MacroRules, input: &tt::Subtree, ) -> ExpandResult { - let (mut result, mut err) = (tt::Subtree::default(), Some(ExpandError::NoMatchingRule)); + let (mut result, mut left_over, mut err) = (tt::Subtree::default(), usize::max_value(), Some(ExpandError::NoMatchingRule)); for rule in &rules.rules { - let (res, e) = expand_rule(rule, input); + let ((res, left), e) = expand_rule(rule, input); if e.is_none() { // if we find a rule that applies without errors, we're done return (res, None); } - // TODO decide which result is better - result = res; - err = e; + // use the rule if we matched more tokens + if left < left_over { + result = res; + err = e; + left_over = left; + } } (result, err) } -fn expand_rule(rule: &crate::Rule, input: &tt::Subtree) -> ExpandResult { - let (bindings, bindings_err) = dbg!(matcher::match_(&rule.lhs, input)); +fn expand_rule(rule: &crate::Rule, input: &tt::Subtree) -> ExpandResult<(tt::Subtree, usize)> { + let ((bindings, left_over), bindings_err) = dbg!(matcher::match_(&rule.lhs, input)); let (res, transcribe_err) = dbg!(transcriber::transcribe(&rule.rhs, &bindings)); - (res, bindings_err.or(transcribe_err)) + ((res, left_over), bindings_err.or(transcribe_err)) } /// The actual algorithm for expansion is not too hard, but is pretty tricky. -- cgit v1.2.3 From 0f3a54dd4d439a6598526144c4ecccee9c5f1362 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sat, 14 Mar 2020 20:24:18 +0100 Subject: wip --- crates/ra_mbe/src/mbe_expander.rs | 49 +++++++++++++++++++++++---------------- 1 file changed, 29 insertions(+), 20 deletions(-) (limited to 'crates/ra_mbe/src/mbe_expander.rs') diff --git a/crates/ra_mbe/src/mbe_expander.rs b/crates/ra_mbe/src/mbe_expander.rs index 5083d5410..b2faa86d2 100644 --- a/crates/ra_mbe/src/mbe_expander.rs +++ b/crates/ra_mbe/src/mbe_expander.rs @@ -8,33 +8,44 @@ mod transcriber; use ra_syntax::SmolStr; use rustc_hash::FxHashMap; -use crate::{ExpandResult, ExpandError}; - -pub(crate) fn expand( - rules: &crate::MacroRules, - input: &tt::Subtree, -) -> ExpandResult { - let (mut result, mut left_over, mut err) = (tt::Subtree::default(), usize::max_value(), Some(ExpandError::NoMatchingRule)); +use crate::{ExpandError, ExpandResult}; + +pub(crate) fn expand(rules: &crate::MacroRules, input: &tt::Subtree) -> ExpandResult { + let (mut result, mut unmatched_tokens, mut unmatched_patterns, mut err) = ( + tt::Subtree::default(), + usize::max_value(), + usize::max_value(), + Some(ExpandError::NoMatchingRule), + ); for rule in &rules.rules { - let ((res, left), e) = expand_rule(rule, input); + let ((res, tokens, patterns), e) = expand_rule(rule, input); if e.is_none() { // if we find a rule that applies without errors, we're done return (res, None); } - // use the rule if we matched more tokens - if left < left_over { + // use the rule if we matched more tokens, or had fewer patterns left + if tokens < unmatched_tokens || tokens == unmatched_tokens && patterns < unmatched_patterns + { result = res; err = e; - left_over = left; + unmatched_tokens = tokens; + unmatched_patterns = patterns; } } (result, err) } -fn expand_rule(rule: &crate::Rule, input: &tt::Subtree) -> ExpandResult<(tt::Subtree, usize)> { - let ((bindings, left_over), bindings_err) = dbg!(matcher::match_(&rule.lhs, input)); - let (res, transcribe_err) = dbg!(transcriber::transcribe(&rule.rhs, &bindings)); - ((res, left_over), bindings_err.or(transcribe_err)) +fn expand_rule( + rule: &crate::Rule, + input: &tt::Subtree, +) -> ExpandResult<(tt::Subtree, usize, usize)> { + dbg!(&rule.lhs); + let (match_result, bindings_err) = dbg!(matcher::match_(&rule.lhs, input)); + let (res, transcribe_err) = dbg!(transcriber::transcribe(&rule.rhs, &match_result.bindings)); + ( + (res, match_result.unmatched_tokens, match_result.unmatched_patterns), + bindings_err.or(transcribe_err), + ) } /// The actual algorithm for expansion is not too hard, but is pretty tricky. @@ -149,10 +160,7 @@ mod tests { crate::MacroRules::parse(&definition_tt).unwrap() } - fn expand_first( - rules: &crate::MacroRules, - invocation: &str, - ) -> ExpandResult { + fn expand_first(rules: &crate::MacroRules, invocation: &str) -> ExpandResult { let source_file = ast::SourceFile::parse(invocation).ok().unwrap(); let macro_invocation = source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap(); @@ -160,6 +168,7 @@ mod tests { let (invocation_tt, _) = ast_to_token_tree(¯o_invocation.token_tree().unwrap()).unwrap(); - expand_rule(&rules.rules[0], &invocation_tt) + let expanded = expand_rule(&rules.rules[0], &invocation_tt); + ((expanded.0).0, expanded.1) } } -- cgit v1.2.3 From c32529ddd0d66a219226dd63da2d4b1825375c0e Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 15 Mar 2020 11:17:13 +0100 Subject: Get tests working --- crates/ra_mbe/src/mbe_expander.rs | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'crates/ra_mbe/src/mbe_expander.rs') diff --git a/crates/ra_mbe/src/mbe_expander.rs b/crates/ra_mbe/src/mbe_expander.rs index b2faa86d2..c2a5702f0 100644 --- a/crates/ra_mbe/src/mbe_expander.rs +++ b/crates/ra_mbe/src/mbe_expander.rs @@ -11,6 +11,7 @@ use rustc_hash::FxHashMap; use crate::{ExpandError, ExpandResult}; pub(crate) fn expand(rules: &crate::MacroRules, input: &tt::Subtree) -> ExpandResult { + eprintln!("expanding input: {:?}", input); let (mut result, mut unmatched_tokens, mut unmatched_patterns, mut err) = ( tt::Subtree::default(), usize::max_value(), @@ -39,9 +40,8 @@ fn expand_rule( rule: &crate::Rule, input: &tt::Subtree, ) -> ExpandResult<(tt::Subtree, usize, usize)> { - dbg!(&rule.lhs); - let (match_result, bindings_err) = dbg!(matcher::match_(&rule.lhs, input)); - let (res, transcribe_err) = dbg!(transcriber::transcribe(&rule.rhs, &match_result.bindings)); + let (match_result, bindings_err) = matcher::match_(&rule.lhs, input); + let (res, transcribe_err) = transcriber::transcribe(&rule.rhs, &match_result.bindings); ( (res, match_result.unmatched_tokens, match_result.unmatched_patterns), bindings_err.or(transcribe_err), -- cgit v1.2.3 From 035db0fbb94e35c78cc76798844db06bd6ad8451 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 15 Mar 2020 11:26:54 +0100 Subject: Add test, remove printlns --- crates/ra_mbe/src/mbe_expander.rs | 1 - 1 file changed, 1 deletion(-) (limited to 'crates/ra_mbe/src/mbe_expander.rs') diff --git a/crates/ra_mbe/src/mbe_expander.rs b/crates/ra_mbe/src/mbe_expander.rs index c2a5702f0..5fb8414b3 100644 --- a/crates/ra_mbe/src/mbe_expander.rs +++ b/crates/ra_mbe/src/mbe_expander.rs @@ -11,7 +11,6 @@ use rustc_hash::FxHashMap; use crate::{ExpandError, ExpandResult}; pub(crate) fn expand(rules: &crate::MacroRules, input: &tt::Subtree) -> ExpandResult { - eprintln!("expanding input: {:?}", input); let (mut result, mut unmatched_tokens, mut unmatched_patterns, mut err) = ( tt::Subtree::default(), usize::max_value(), -- cgit v1.2.3 From 0660dd10d203cba4069b48d00d02ec9935a916f0 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 15 Mar 2020 14:37:30 +0100 Subject: Fix performance problem --- crates/ra_mbe/src/mbe_expander.rs | 67 +++++++++++++++++++++------------------ 1 file changed, 36 insertions(+), 31 deletions(-) (limited to 'crates/ra_mbe/src/mbe_expander.rs') diff --git a/crates/ra_mbe/src/mbe_expander.rs b/crates/ra_mbe/src/mbe_expander.rs index 5fb8414b3..1328e4349 100644 --- a/crates/ra_mbe/src/mbe_expander.rs +++ b/crates/ra_mbe/src/mbe_expander.rs @@ -11,40 +11,45 @@ use rustc_hash::FxHashMap; use crate::{ExpandError, ExpandResult}; pub(crate) fn expand(rules: &crate::MacroRules, input: &tt::Subtree) -> ExpandResult { - let (mut result, mut unmatched_tokens, mut unmatched_patterns, mut err) = ( - tt::Subtree::default(), - usize::max_value(), - usize::max_value(), - Some(ExpandError::NoMatchingRule), - ); - for rule in &rules.rules { - let ((res, tokens, patterns), e) = expand_rule(rule, input); - if e.is_none() { + expand_rules(&rules.rules, input) +} + +fn expand_rules(rules: &[crate::Rule], input: &tt::Subtree) -> ExpandResult { + let mut match_: Option<(matcher::Match, &crate::Rule)> = None; + let mut err = Some(ExpandError::NoMatchingRule); + for rule in rules { + let (new_match, bindings_err) = matcher::match_(&rule.lhs, input); + if bindings_err.is_none() { // if we find a rule that applies without errors, we're done - return (res, None); + eprintln!("match without errors: {:?}", new_match); + let (res, transcribe_err) = transcriber::transcribe(&rule.rhs, &new_match.bindings); + eprintln!("transcribe_err = {:?}", transcribe_err); + if transcribe_err.is_none() { + return (res, None); + } } // use the rule if we matched more tokens, or had fewer patterns left - if tokens < unmatched_tokens || tokens == unmatched_tokens && patterns < unmatched_patterns - { - result = res; - err = e; - unmatched_tokens = tokens; - unmatched_patterns = patterns; + if let Some((prev_match, _)) = &match_ { + if new_match.unmatched_tokens < prev_match.unmatched_tokens + || new_match.unmatched_tokens == prev_match.unmatched_tokens + && new_match.unmatched_patterns < prev_match.unmatched_patterns + || err.is_some() && bindings_err.is_none() + { + match_ = Some((new_match, rule)); + err = bindings_err; + } + } else { + match_ = Some((new_match, rule)); + err = bindings_err; } } - (result, err) -} - -fn expand_rule( - rule: &crate::Rule, - input: &tt::Subtree, -) -> ExpandResult<(tt::Subtree, usize, usize)> { - let (match_result, bindings_err) = matcher::match_(&rule.lhs, input); - let (res, transcribe_err) = transcriber::transcribe(&rule.rhs, &match_result.bindings); - ( - (res, match_result.unmatched_tokens, match_result.unmatched_patterns), - bindings_err.or(transcribe_err), - ) + if let Some((match_, rule)) = match_ { + // if we got here, there was no match without errors + let (result, transcribe_err) = transcriber::transcribe(&rule.rhs, &match_.bindings); + (result, err.or(transcribe_err)) + } else { + (tt::Subtree::default(), err) + } } /// The actual algorithm for expansion is not too hard, but is pretty tricky. @@ -167,7 +172,7 @@ mod tests { let (invocation_tt, _) = ast_to_token_tree(¯o_invocation.token_tree().unwrap()).unwrap(); - let expanded = expand_rule(&rules.rules[0], &invocation_tt); - ((expanded.0).0, expanded.1) + let expanded = expand_rules(&rules.rules, &invocation_tt); + (expanded.0, expanded.1) } } -- cgit v1.2.3 From f3c6a2e3dbe477a7e0ac714a5bdbda6e8838fcfa Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 15 Mar 2020 15:15:56 +0100 Subject: Fix remaining test failure --- crates/ra_mbe/src/mbe_expander.rs | 2 -- 1 file changed, 2 deletions(-) (limited to 'crates/ra_mbe/src/mbe_expander.rs') diff --git a/crates/ra_mbe/src/mbe_expander.rs b/crates/ra_mbe/src/mbe_expander.rs index 1328e4349..204c30e3d 100644 --- a/crates/ra_mbe/src/mbe_expander.rs +++ b/crates/ra_mbe/src/mbe_expander.rs @@ -21,9 +21,7 @@ fn expand_rules(rules: &[crate::Rule], input: &tt::Subtree) -> ExpandResult Date: Mon, 16 Mar 2020 12:22:10 +0100 Subject: Turn ExpandResult into struct --- crates/ra_mbe/src/mbe_expander.rs | 16 +++++++++------- 1 file changed, 9 insertions(+), 7 deletions(-) (limited to 'crates/ra_mbe/src/mbe_expander.rs') diff --git a/crates/ra_mbe/src/mbe_expander.rs b/crates/ra_mbe/src/mbe_expander.rs index 204c30e3d..0a4d73dda 100644 --- a/crates/ra_mbe/src/mbe_expander.rs +++ b/crates/ra_mbe/src/mbe_expander.rs @@ -18,12 +18,13 @@ fn expand_rules(rules: &[crate::Rule], input: &tt::Subtree) -> ExpandResult = None; let mut err = Some(ExpandError::NoMatchingRule); for rule in rules { - let (new_match, bindings_err) = matcher::match_(&rule.lhs, input); + let ExpandResult(new_match, bindings_err) = matcher::match_(&rule.lhs, input); if bindings_err.is_none() { // if we find a rule that applies without errors, we're done - let (res, transcribe_err) = transcriber::transcribe(&rule.rhs, &new_match.bindings); + let ExpandResult(res, transcribe_err) = + transcriber::transcribe(&rule.rhs, &new_match.bindings); if transcribe_err.is_none() { - return (res, None); + return ExpandResult::ok(res); } } // use the rule if we matched more tokens, or had fewer patterns left @@ -43,10 +44,11 @@ fn expand_rules(rules: &[crate::Rule], input: &tt::Subtree) -> ExpandResult Date: Mon, 16 Mar 2020 18:04:07 +0100 Subject: Some cleanup --- crates/ra_mbe/src/mbe_expander.rs | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) (limited to 'crates/ra_mbe/src/mbe_expander.rs') diff --git a/crates/ra_mbe/src/mbe_expander.rs b/crates/ra_mbe/src/mbe_expander.rs index 0a4d73dda..3c00e3b64 100644 --- a/crates/ra_mbe/src/mbe_expander.rs +++ b/crates/ra_mbe/src/mbe_expander.rs @@ -20,18 +20,20 @@ fn expand_rules(rules: &[crate::Rule], input: &tt::Subtree) -> ExpandResult Date: Mon, 16 Mar 2020 18:38:10 +0100 Subject: Some more refactoring --- crates/ra_mbe/src/mbe_expander.rs | 22 ++++++++++++---------- 1 file changed, 12 insertions(+), 10 deletions(-) (limited to 'crates/ra_mbe/src/mbe_expander.rs') diff --git a/crates/ra_mbe/src/mbe_expander.rs b/crates/ra_mbe/src/mbe_expander.rs index 3c00e3b64..7adb70d45 100644 --- a/crates/ra_mbe/src/mbe_expander.rs +++ b/crates/ra_mbe/src/mbe_expander.rs @@ -16,10 +16,15 @@ pub(crate) fn expand(rules: &crate::MacroRules, input: &tt::Subtree) -> ExpandRe fn expand_rules(rules: &[crate::Rule], input: &tt::Subtree) -> ExpandResult { let mut match_: Option<(matcher::Match, &crate::Rule)> = None; - let mut err = Some(ExpandError::NoMatchingRule); for rule in rules { - let ExpandResult(new_match, bindings_err) = matcher::match_(&rule.lhs, input); - if bindings_err.is_none() { + let new_match = match matcher::match_(&rule.lhs, input) { + Ok(m) => m, + Err(_e) => { + // error in pattern parsing + continue; + } + }; + if new_match.err.is_none() { // If we find a rule that applies without errors, we're done. // Unconditionally returning the transcription here makes the // `test_repeat_bad_var` test fail. @@ -32,25 +37,22 @@ fn expand_rules(rules: &[crate::Rule], input: &tt::Subtree) -> ExpandResult Date: Mon, 16 Mar 2020 18:46:08 +0100 Subject: Small fixes --- crates/ra_mbe/src/mbe_expander.rs | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) (limited to 'crates/ra_mbe/src/mbe_expander.rs') diff --git a/crates/ra_mbe/src/mbe_expander.rs b/crates/ra_mbe/src/mbe_expander.rs index 7adb70d45..b1eacf124 100644 --- a/crates/ra_mbe/src/mbe_expander.rs +++ b/crates/ra_mbe/src/mbe_expander.rs @@ -34,8 +34,7 @@ fn expand_rules(rules: &[crate::Rule], input: &tt::Subtree) -> ExpandResult