+{

+ "problemMatcher": [

+ {

+ "owner": "rustfmt",

+ "severity": "warning",

+ "pattern": [

+ {

+ "regexp": "^(Diff in (.+)) at line (\\d+):$",

+ "message": 1,

+ "file": 2,

+ "line": 3

+ }

+ ]

+ },

+ {

+ "owner": "clippy",

+ "pattern": [

+ {

+ "regexp": "^(?:\\x1b\\[[\\d;]+m)*(warning|warn|error)(?:\\x1b\\[[\\d;]+m)*(\\[(.*)\\])?(?:\\x1b\\[[\\d;]+m)*:(?:\\x1b\\[[\\d;]+m)* ([^\\x1b]*)(?:\\x1b\\[[\\d;]+m)*$",

+ "severity": 1,

+ "message": 4,

+ "code": 3

+ },

+ {

+ "regexp": "^(?:\\x1b\\[[\\d;]+m)*\\s*(?:\\x1b\\[[\\d;]+m)*\\s*--> (?:\\x1b\\[[\\d;]+m)*(.*):(\\d*):(\\d*)(?:\\x1b\\[[\\d;]+m)*$",

+ "file": 1,

+ "line": 2,

+ "column": 3

+ }

+ ]

+ }

+ ]

+}

+ uses: actions/checkout@v4

+ - uses: actions/checkout@v4

+ uses: actions/checkout@v4

+ # https://github.com/actions-rust-lang/setup-rust-toolchain/blob/main/rust.json

+ - name: Install Rust Problem Matcher

+ if: matrix.os == 'ubuntu-latest'

+ run: echo "::add-matcher::.github/rust.json"

+ - name: rustfmt

+ if: matrix.os == 'ubuntu-latest'

+ run: cargo fmt -- --check

+

+ uses: actions/checkout@v4

+ uses: actions/checkout@v4

+ uses: actions/setup-node@v4

+ node-version: 18

+ uses: actions/checkout@v4

+ uses: actions/cache@v4

+ uses: actions/checkout@v4

+ uses: actions/cache@v4

+ uses: actions/cache@v4

+ uses: actions/checkout@v4

+ uses: actions/cache@v4

+ uses: actions/cache@v4

+ uses: actions/checkout@v4

+ uses: actions/checkout@v4

+ uses: actions/checkout@v4

+ uses: actions/setup-node@v4

+ node-version: 18

+ uses: actions/checkout@v4

+ uses: actions/setup-node@v4

+ node-version: 18

+ uses: actions/checkout@v4

+ uses: actions/checkout@v4

+ "ra-ap-rustc_lexer",

+version = "0.37.0"

+checksum = "df5a0ba0d08af366cf235dbe8eb7226cced7a4fe502c98aa434ccf416defd746"

+ "ra-ap-rustc_index_macros 0.37.0",

+version = "0.37.0"

+checksum = "1971ebf9a701e0e68387c264a32517dcb4861ad3a4862f2e2803c1121ade20d5"

+version = "0.37.0"

+checksum = "2c3c0e7ca9c5bdc66e3b590688e237a22ac47a48e4eac7f46b05b2abbfaf0abd"

+ "ra-ap-rustc_index 0.37.0",

+ra-ap-rustc_pattern_analysis = { version = "0.37.0", default-features = false }

+

+ pub fn new(name: CrateName, crate_id: CrateId) -> Self {

+ Self { name, crate_id, prelude: true }

+ pub fn with_prelude(name: CrateName, crate_id: CrateId, prelude: bool) -> Self {

+ Self { name, crate_id, prelude }

+ pub fn len(&self) -> usize {

+ self.arena.len()

+ }

+

+ /// If the crate dependencies were sorted, the resulting graph from this `extend` call will also

+ /// have the crate dependencies sorted.

+ ///

+ /// Returns a mapping from `other`'s crate ids to the new crate ids in `self`.

+ merge: impl Fn((CrateId, &mut CrateData), (CrateId, &CrateData)) -> bool,

+ ) -> FxHashMap<CrateId, CrateId> {

+ let m = self.len();

+ let res = self

+ .arena

+ .iter_mut()

+ .take(m)

+ .find_map(|(id, data)| merge((id, data), (topo, &crate_data)).then_some(id));

+

+ let new_id =

+ if let Some(res) = res { res } else { self.arena.alloc(crate_data.clone()) };

+ id_map.insert(topo, new_id);

+ id_map

+ self.arena[std]

+ .dependencies

+ .push(Dependency::new(CrateName::new("cfg_if").unwrap(), cfg_if));

+ use crate::CrateOrigin;

+ .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2,))

+ .add_dep(crate2, Dependency::new(CrateName::new("crate3").unwrap(), crate3,))

+ .add_dep(crate3, Dependency::new(CrateName::new("crate1").unwrap(), crate1,))

+ .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2,))

+ .add_dep(crate2, Dependency::new(CrateName::new("crate2").unwrap(), crate2,))

+ .add_dep(crate1, Dependency::new(CrateName::new("crate2").unwrap(), crate2,))

+ .add_dep(crate2, Dependency::new(CrateName::new("crate3").unwrap(), crate3,))

+ Dependency::new(CrateName::normalize_dashes("crate-name-with-dashes"), crate2,)

+ vec![Dependency::new(CrateName::new("crate_name_with_dashes").unwrap(), crate2,)]

+

+ // FIXME: Consider removing this, making HirDatabase::target_data_layout an input query

+ #[salsa::input]

+ fn data_layout(&self, krate: CrateId) -> TargetLayoutLoadResult;

+

+ #[salsa::input]

+ fn toolchain(&self, krate: CrateId) -> Option<Version>;

+

+ #[salsa::transparent]

+ fn toolchain_channel(&self, krate: CrateId) -> Option<ReleaseChannel>;

+}

+

+fn toolchain_channel(db: &dyn SourceDatabase, krate: CrateId) -> Option<ReleaseChannel> {

+ db.toolchain(krate).as_ref().and_then(|v| ReleaseChannel::from_str(&v.pre))

+use paths::{AbsPath, AbsPathBuf};

+use toolchain::Tool;

+ sysroot_root: Option<AbsPathBuf>,

+ let actor = FlycheckActor::new(id, sender, config, sysroot_root, workspace_root);

+ pub fn restart_workspace(&self, saved_file: Option<AbsPathBuf>) {

+ self.sender.send(StateChange::Restart { package: None, saved_file }).unwrap();

+ self.sender

+ .send(StateChange::Restart { package: Some(package), saved_file: None })

+ .unwrap();

+ Restart { package: Option<String>, saved_file: Option<AbsPathBuf> },

+ sysroot_root: Option<AbsPathBuf>,

+const SAVED_FILE_PLACEHOLDER: &str = "$saved_file";

+

+ sysroot_root: Option<AbsPathBuf>,

+ FlycheckActor {

+ id,

+ sender,

+ config,

+ sysroot_root,

+ root: workspace_root,

+ command_handle: None,

+ }

+ Event::RequestStateChange(StateChange::Restart { package, saved_file }) => {

+ let command =

+ match self.check_command(package.as_deref(), saved_file.as_deref()) {

+ Some(c) => c,

+ None => continue,

+ };

+ /// Construct a `Command` object for checking the user's code. If the user

+ /// has specified a custom command with placeholders that we cannot fill,

+ /// return None.

+ fn check_command(

+ &self,

+ package: Option<&str>,

+ saved_file: Option<&AbsPath>,

+ ) -> Option<Command> {

+ let mut cmd = Command::new(Tool::Cargo.path());

+ if let Some(sysroot_root) = &self.sysroot_root {

+ cmd.env("RUSTUP_TOOLCHAIN", AsRef::<std::path::Path>::as_ref(sysroot_root));

+ }

+ (cmd, extra_args.clone())

+ if args.contains(&SAVED_FILE_PLACEHOLDER.to_owned()) {

+ // If the custom command has a $saved_file placeholder, and

+ // we're saving a file, replace the placeholder in the arguments.

+ if let Some(saved_file) = saved_file {

+ let args = args

+ .iter()

+ .map(|arg| {

+ if arg == SAVED_FILE_PLACEHOLDER {

+ saved_file.to_string()

+ } else {

+ arg.clone()

+ }

+ })

+ .collect();

+ (cmd, args)

+ } else {

+ // The custom command has a $saved_file placeholder,

+ // but we had an IDE event that wasn't a file save. Do nothing.

+ return None;

+ }

+ } else {

+ (cmd, args.clone())

+ }

+ Some(cmd)

+ // FIXME: We should be never getting `None` here.

+ match src.value.get(it.local_id()) {

+ Some(val) => RawAttrs::from_attrs_owner(

+ db.upcast(),

+ src.with_value(val),

+ db.span_map(src.file_id).as_ref(),

+ ),

+ None => RawAttrs::EMPTY,

+ }

+ // FIXME: We should be never getting `None` here.

+ match src.value.get(it.local_id()) {

+ Some(val) => RawAttrs::from_attrs_owner(

+ db.upcast(),

+ src.with_value(val),

+ db.span_map(src.file_id).as_ref(),

+ ),

+ None => RawAttrs::EMPTY,

+ }

+ // FIXME: We should be never getting `None` here.

+ match src.value.get(it.local_id) {

+ Some(val) => RawAttrs::from_attrs_owner(

+ db.upcast(),

+ src.with_value(val),

+ db.span_map(src.file_id).as_ref(),

+ ),

+ None => RawAttrs::EMPTY,

+ }

+ ast::Expr::BecomeExpr(e) => {

+ let expr =

+ e.expr().map(|e| self.collect_expr(e)).unwrap_or_else(|| self.missing_expr());

+ self.alloc_expr(Expr::Become { expr }, syntax_ptr)

+ }

+ ast::Stmt::Item(_item) => statements.push(Statement::Item),

+ Expr::Become { expr } => {

+ w!(self, "become");

+ self.whitespace();

+ self.print_expr(*expr);

+ }

+ Statement::Item => (),

+ Statement::Item => (),

+ self.diagnostics.push(DefDiagnostic::unresolved_proc_macro(

+ self.module_id.local_id,

+ loc.kind,

+ loc.def.krate,

+ ));

+

+ continue 'attrs;

+ }

+ if exp.is_disabled() {

+ self.attr_calls.push((ast_id, call_id));

+

+ return ExpandResult::ok(None);

+ return ExpandResult::only_err(ExpandError::RecursionOverflow);

+ let choose = |new: (ModPath, _), old: (ModPath, _)| {

+ let (new_path, _) = &new;

+ let (old_path, _) = &old;

+ let new_has_prelude = new_path.segments().iter().any(|seg| seg == &known::prelude);

+ let old_has_prelude = old_path.segments().iter().any(|seg| seg == &known::prelude);

+ (true, false, true) | (false, true, false) => new,

+ (true, false, false) | (false, true, true) => old,

+ // no prelude difference in the paths, so pick the shorter one

+ let new_path_is_shorter = new_path

+ .len()

+ .cmp(&old_path.len())

+ .then_with(|| new_path.textual_len().cmp(&old_path.textual_len()))

+ .is_lt();

+ if new_path_is_shorter {

+ new

+ old

+ name if name == &known::alloc => 1,

+ name if name == &known::std => 2,

+

+ #[test]

+ fn respect_segment_length() {

+ check_found_path(

+ r#"

+//- /main.rs crate:main deps:petgraph

+$0

+//- /petgraph.rs crate:petgraph

+pub mod graph {

+ pub use crate::graph_impl::{

+ NodeIndex

+ };

+}

+

+mod graph_impl {

+ pub struct NodeIndex<Ix>(Ix);

+}

+

+pub mod stable_graph {

+ #[doc(no_inline)]

+ pub use crate::graph::{NodeIndex};

+}

+

+pub mod prelude {

+ #[doc(no_inline)]

+ pub use crate::graph::{NodeIndex};

+}

+"#,

+ "petgraph::graph::NodeIndex",

+ "petgraph::graph::NodeIndex",

+ "petgraph::graph::NodeIndex",

+ "petgraph::graph::NodeIndex",

+ );

+ }

+ // FIXME: Fold this into Block with an unsafe flag?

+ Become {

+ expr: ExprId,

+ },

+ // At the moment, we only use this to figure out if a return expression

+ // is really the last statement of a block. See #16566

+ Item,

+ Statement::Item => (),

+ Expr::Become { expr } => f(*expr),

+/* error: mismatched delimiters */"#]],

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+/* error: macro definition has parse errors */

+ /* error: macro definition has parse errors */;

+ /* error: macro definition has parse errors */;

+ /* error: macro definition has parse errors */;

+

+#[test]

+fn regression_16529() {

+ check(

+ r#"

+mod any {

+ #[macro_export]

+ macro_rules! nameable {

+ {

+ struct $name:ident[$a:lifetime]

+ } => {

+ $crate::any::nameable! {

+ struct $name[$a]

+ a

+ }

+ };

+ {

+ struct $name:ident[$a:lifetime]

+ a

+ } => {};

+ }

+ pub use nameable;

+

+ nameable! {

+ Name['a]

+ }

+}

+"#,

+ expect![[r#"

+mod any {

+ #[macro_export]

+ macro_rules! nameable {

+ {

+ struct $name:ident[$a:lifetime]

+ } => {

+ $crate::any::nameable! {

+ struct $name[$a]

+ a

+ }

+ };

+ {

+ struct $name:ident[$a:lifetime]

+ a

+ } => {};

+ }

+ pub use nameable;

+

+ /* error: unexpected token in input */$crate::any::nameable! {

+ struct $name[$a]a

+ }

+}

+"#]],

+ );

+}

+/* error: macro definition has parse errors */

+/* error: mismatched delimiters */

+ disabled: false,

+ builtin_attr_macro::{find_builtin_attr, BuiltinAttrExpander},

+ if it.disabled {

+ CustomProcMacroExpander::disabled()

+ } else {

+ CustomProcMacroExpander::new(

+ hir_expand::proc_macro::ProcMacroId::new(idx as u32),

+ )

+ },

+

+ #[derive(PartialEq, Eq)]

+ enum Resolved {

+ Yes,

+ No,

+ }

+

+ let mut retain = |directive: &MacroDirective| {

+

+ return Resolved::Yes;

+ return Resolved::Yes;

+ Resolved::Yes

+ _ => return Resolved::No,

+

+ if let MacroDefId {

+ kind:

+ MacroDefKind::BuiltInAttr(

+ BuiltinAttrExpander::Derive | BuiltinAttrExpander::DeriveConst,

+ _,

+ ),

+ ..

+ } = def

+ {

+ // If proc attribute macro expansion is disabled, skip expanding it here

+ if !self.db.expand_proc_attr_macros() {

+ return recollect_without(self);

+ }

+ // If there's no expander for the proc macro (e.g.

+ // because proc macros are disabled, or building the

+ // proc macro crate failed), report this and skip

+ // expansion like we would if it was disabled

+ if exp.is_dummy() {

+ self.def_map.diagnostics.push(DefDiagnostic::unresolved_proc_macro(

+ directive.module_id,

+ self.db.lookup_intern_macro_call(call_id).kind,

+ def.krate,

+ ));

+ return recollect_without(self);

+ }

+ if exp.is_disabled() {

+ return Resolved::Yes;

+ Resolved::No

+ };

+ macros.retain(|it| retain(it) == Resolved::No);

+

+ if self.def_collector.def_map.block.is_none()

+ && self.def_collector.is_proc_macro

+ && self.module_id == DefMap::ROOT

+ {

+ // FIXME: if there were errors, this might've been in the eager expansion from an

+ // FIXME: This is used for a lot of things, unresolved proc macros, disabled proc macros, etc

+ // yet the diagnostic handler in ide-diagnostics has to figure out what happened because this

+ // struct loses all that information!

+ Some(unquoted) => ExpandError::other(unquoted.into_boxed_str()),

+use base_db::{

+ salsa::Durability, CrateGraph, CrateId, FileChange, SourceDatabaseExt, SourceRoot,

+ TargetLayoutLoadResult, Version,

+};

+use la_arena::RawIdx;

+ pub toolchains: Option<Vec<Option<Version>>>,

+ pub target_data_layouts: Option<Vec<TargetLayoutLoadResult>>,

+ if let Some(target_data_layouts) = self.target_data_layouts {

+ for (id, val) in target_data_layouts.into_iter().enumerate() {

+ db.set_data_layout_with_durability(

+ CrateId::from_raw(RawIdx::from(id as u32)),

+ val,

+ Durability::HIGH,

+ );

+ }

+ }

+ if let Some(toolchains) = self.toolchains {

+ for (id, val) in toolchains.into_iter().enumerate() {

+ db.set_toolchain_with_durability(

+ CrateId::from_raw(RawIdx::from(id as u32)),

+ val,

+ Durability::HIGH,

+ );

+ }

+ }

+ pub fn set_toolchains(&mut self, toolchains: Vec<Option<Version>>) {

+ self.toolchains = Some(toolchains);

+ }

+

+ pub fn set_target_data_layouts(&mut self, target_data_layouts: Vec<TargetLayoutLoadResult>) {

+ self.target_data_layouts = Some(target_data_layouts);

+ }

+

+ ) -> ValueResult<(Arc<tt::Subtree>, SyntaxFixupUndoInfo), Arc<Box<[SyntaxError]>>>;

+ // ) -> ValueResult<Arc<(tt::Subtree, SyntaxFixupUndoInfo)>, Arc<Box<[SyntaxError]>>> {

+) -> ValueResult<(Arc<tt::Subtree>, SyntaxFixupUndoInfo), Arc<Box<[SyntaxError]>>> {

+ ValueResult::ok((arg.clone(), SyntaxFixupUndoInfo::NONE))

+ let dummy_tt = |kind| {

+ (

+ Arc::new(tt::Subtree {

+ delimiter: tt::Delimiter {

+ open: loc.call_site,

+ close: loc.call_site,

+ kind,

+ },

+ token_trees: Box::default(),

+ }),

+ SyntaxFixupUndoInfo::default(),

+ )

+ };

+

+ let Some(tt) = node.token_tree() else {

+ return ValueResult::new(

+ dummy_tt(tt::DelimiterKind::Invisible),

+ Arc::new(Box::new([SyntaxError::new_at_offset(

+ "missing token tree".to_owned(),

+ offset,

+ )])),

+ );

+ };

+ let first = tt.left_delimiter_token().map(|it| it.kind()).unwrap_or(T!['(']);

+ let last = tt.right_delimiter_token().map(|it| it.kind()).unwrap_or(T![.]);

+

+ let mismatched_delimiters = !matches!(

+ (first, last),

+ (T!['('], T![')']) | (T!['['], T![']']) | (T!['{'], T!['}'])

+ );

+ if mismatched_delimiters {

+ // Don't expand malformed (unbalanced) macro invocations. This is

+ // less than ideal, but trying to expand unbalanced macro calls

+ // sometimes produces pathological, deeply nested code which breaks

+ // all kinds of things.

+ //

+ // So instead, we'll return an empty subtree here

+ cov_mark::hit!(issue9358_bad_macro_stack_overflow);

+

+ let kind = match first {

+ _ if loc.def.is_proc_macro() => tt::DelimiterKind::Invisible,

+ T!['('] => tt::DelimiterKind::Parenthesis,

+ T!['['] => tt::DelimiterKind::Bracket,

+ T!['{'] => tt::DelimiterKind::Brace,

+ _ => tt::DelimiterKind::Invisible,

+ };

+ return ValueResult::new(

+ dummy_tt(kind),

+ Arc::new(Box::new([SyntaxError::new_at_offset(

+ "mismatched delimiters".to_owned(),

+ offset,

+ )])),

+ );

+ tt.syntax().clone()

+ [] => ValueResult::ok((Arc::new(tt), undo_info)),

+ (Arc::new(tt), undo_info),

+ ValueResult::ok((Arc::new(tt), undo_info))

+ let ValueResult { value: (macro_arg, undo_info), err } = db.macro_arg(macro_call_id);

+ let format_parse_err = |err: Arc<Box<[SyntaxError]>>| {

+ let mut buf = String::new();

+ for err in &**err {

+ use std::fmt::Write;

+ _ = write!(buf, "{}, ", err);

+ }

+ buf.pop();

+ buf.pop();

+ ExpandError::other(buf)

+ let res = match loc.def.kind {

+ err: err.map(format_parse_err),

+ };

+ ExpandResult {

+ value: res.value,

+ // if the arg had parse errors, show them instead of the expansion errors

+ err: err.map(format_parse_err).or(res.err),

+ let (macro_arg, undo_info) = db.macro_arg(id).value;

+ let toolchain = db.toolchain(loc.def.krate);

+ Some(_) => ExpandResult::new(

+ ExpandError::MacroDefinition,

+ let toolchain = db.toolchain(krate);

+ Some(_) => ExpandResult::new(

+ ExpandError::MacroDefinition,

+ let toolchain = db.toolchain(def_crate);

+ /// The macro expansion is disabled.

+ MacroDisabled,

+ MacroDefinition,

+ RecursionOverflow,

+ ExpandError::RecursionOverflow => f.write_str("overflow expanding the original macro"),

+ ExpandError::MacroDisabled => f.write_str("macro disabled"),

+ ExpandError::MacroDefinition => f.write_str("macro definition has parse errors"),

+ // FIXME: This shouldn't be here, we can derive this from `invoc_attr_index`

+ // but we need to fix the `cfg_attr` handling first.

+ let (macro_arg, _) = db.macro_arg(macro_file.macro_call_id).value;

+ pub fn textual_len(&self) -> usize {

+ let base = match self.kind {

+ PathKind::Plain => 0,

+ PathKind::Super(0) => "self".len(),

+ PathKind::Super(i) => "super".len() * i as usize,

+ PathKind::Crate => "crate".len(),

+ PathKind::Abs => 0,

+ PathKind::DollarCrate(_) => "$crate".len(),

+ };

+ self.segments()

+ .iter()

+ .map(|segment| segment.as_str().map_or(0, str::len))

+ .fold(base, core::ops::Add::add)

+ }

+

+pub struct ProcMacroId(u32);

+

+impl ProcMacroId {

+ pub fn new(u32: u32) -> Self {

+ ProcMacroId(u32)

+ }

+}

+ pub disabled: bool,

+ const DUMMY_ID: u32 = !0;

+ const DISABLED_ID: u32 = !1;

+

+ assert_ne!(proc_macro_id.0, Self::DUMMY_ID);

+ assert_ne!(proc_macro_id.0, Self::DISABLED_ID);

+ /// A dummy expander that always errors. This is used for proc-macros that are missing, usually

+ /// due to them not being built yet.

+ pub const fn dummy() -> Self {

+ Self { proc_macro_id: ProcMacroId(Self::DUMMY_ID) }

+ }

+

+ /// The macro was not yet resolved.

+ pub const fn is_dummy(&self) -> bool {

+ self.proc_macro_id.0 == Self::DUMMY_ID

+ }

+

+ /// A dummy expander that always errors. This expander is used for macros that have been disabled.

+ pub const fn disabled() -> Self {

+ Self { proc_macro_id: ProcMacroId(Self::DISABLED_ID) }

+ /// The macro is explicitly disabled and cannot be expanded.

+ pub const fn is_disabled(&self) -> bool {

+ self.proc_macro_id.0 == Self::DISABLED_ID

+ ProcMacroId(Self::DUMMY_ID) => ExpandResult::new(

+ ProcMacroId(Self::DISABLED_ID) => ExpandResult::new(

+ tt::Subtree::empty(tt::DelimSpan { open: call_site, close: call_site }),

+ ExpandError::MacroDisabled,

+ ),

+ ExpandError::other("Internal error: proc-macro index out of bounds"),

+ let cx = MatchCheckCtx::new(self.owner.module(db.upcast()), self.owner, db);

+ let pattern_arena = Arena::new();

+ let pat = self.lower_pattern(&cx, arm.pat, db, &body, &mut has_lowering_errors);

+ pat: pattern_arena.alloc(pat),

+ Err(()) => return,

+ ) -> DeconstructedPat<'p> {

+ let pattern = cx.lower_pat(&pattern);

+use tracing::debug;

+ rustc_pattern_analysis::pat::DeconstructedPat<MatchCheckCtx<'p>>;

+ pub(crate) fn new(module: ModuleId, body: DefWithBodyId, db: &'p dyn HirDatabase) -> Self {

+ Self { module, body, db, exhaustive_patterns, min_exhaustive_patterns }

+ let singleton = |pat| vec![pat];

+ let fields: Vec<_>;

+ fields = Vec::new();

+ let mut wilds: Vec<_> = substs

+ fields = wilds

+ let mut wilds: Vec<_> = tys.map(DeconstructedPat::wildcard).collect();

+ fields = wilds;

+ fields = Vec::new();

+ fields = Vec::new();

+ fields = pats.iter().map(|pat| self.lower_pat(pat)).collect();

+ type Error = ();

+ pat: &rustc_pattern_analysis::pat::DeconstructedPat<Self>,

+ fn bug(&self, fmt: fmt::Arguments<'_>) {

+ debug!("{}", fmt)

+ Scalar, TyKind, TypeFlags, Variance,

+ AliasEq, AliasTy, Binders, ClosureId, Const, DomainGoal, GenericArg, Goal, ImplTraitId,

+ InEnvironment, Interner, Lifetime, ProjectionTy, RpitId, Substitution, TraitEnvironment,

+ TraitRef, Ty, TyBuilder, TyExt,

+pub use unify::{could_unify, could_unify_deeply};

+ type_mismatches.retain(|_, mismatch| {

+ chalk_ir::zip::Zip::zip_with(

+ &mut UnknownMismatch(self.db),

+ Variance::Invariant,

+ &mismatch.expected,

+ &mismatch.actual,

+ )

+ .is_ok()

+ });

+/// A zipper that checks for unequal `{unknown}` occurrences in the two types. Used to filter out

+/// mismatch diagnostics that only differ in `{unknown}`. These mismatches are usually not helpful.

+/// As the cause is usually an underlying name resolution problem.

+struct UnknownMismatch<'db>(&'db dyn HirDatabase);

+impl chalk_ir::zip::Zipper<Interner> for UnknownMismatch<'_> {

+ fn zip_tys(&mut self, variance: Variance, a: &Ty, b: &Ty) -> chalk_ir::Fallible<()> {

+ let zip_substs = |this: &mut Self,

+ variances,

+ sub_a: &Substitution,

+ sub_b: &Substitution| {

+ this.zip_substs(variance, variances, sub_a.as_slice(Interner), sub_b.as_slice(Interner))

+ };

+ match (a.kind(Interner), b.kind(Interner)) {

+ (TyKind::Adt(id_a, sub_a), TyKind::Adt(id_b, sub_b)) if id_a == id_b => zip_substs(

+ self,

+ Some(self.unification_database().adt_variance(*id_a)),

+ sub_a,

+ sub_b,

+ )?,

+ (

+ TyKind::AssociatedType(assoc_ty_a, sub_a),

+ TyKind::AssociatedType(assoc_ty_b, sub_b),

+ ) if assoc_ty_a == assoc_ty_b => zip_substs(self, None, sub_a, sub_b)?,

+ (TyKind::Tuple(arity_a, sub_a), TyKind::Tuple(arity_b, sub_b))

+ if arity_a == arity_b =>

+ {

+ zip_substs(self, None, sub_a, sub_b)?

+ }

+ (TyKind::OpaqueType(opaque_ty_a, sub_a), TyKind::OpaqueType(opaque_ty_b, sub_b))

+ if opaque_ty_a == opaque_ty_b =>

+ {

+ zip_substs(self, None, sub_a, sub_b)?

+ }

+ (TyKind::Slice(ty_a), TyKind::Slice(ty_b)) => self.zip_tys(variance, ty_a, ty_b)?,

+ (TyKind::FnDef(fn_def_a, sub_a), TyKind::FnDef(fn_def_b, sub_b))

+ if fn_def_a == fn_def_b =>

+ {

+ zip_substs(

+ self,

+ Some(self.unification_database().fn_def_variance(*fn_def_a)),

+ sub_a,

+ sub_b,

+ )?

+ }

+ (TyKind::Ref(mutability_a, _, ty_a), TyKind::Ref(mutability_b, _, ty_b))

+ if mutability_a == mutability_b =>

+ {

+ self.zip_tys(variance, ty_a, ty_b)?

+ }

+ (TyKind::Raw(mutability_a, ty_a), TyKind::Raw(mutability_b, ty_b))

+ if mutability_a == mutability_b =>

+ {

+ self.zip_tys(variance, ty_a, ty_b)?

+ }

+ (TyKind::Array(ty_a, const_a), TyKind::Array(ty_b, const_b)) if const_a == const_b => {

+ self.zip_tys(variance, ty_a, ty_b)?

+ }

+ (TyKind::Closure(id_a, sub_a), TyKind::Closure(id_b, sub_b)) if id_a == id_b => {

+ zip_substs(self, None, sub_a, sub_b)?

+ }

+ (TyKind::Coroutine(coroutine_a, sub_a), TyKind::Coroutine(coroutine_b, sub_b))

+ if coroutine_a == coroutine_b =>

+ {

+ zip_substs(self, None, sub_a, sub_b)?

+ }

+ (

+ TyKind::CoroutineWitness(coroutine_a, sub_a),

+ TyKind::CoroutineWitness(coroutine_b, sub_b),

+ ) if coroutine_a == coroutine_b => zip_substs(self, None, sub_a, sub_b)?,

+ (TyKind::Function(fn_ptr_a), TyKind::Function(fn_ptr_b))

+ if fn_ptr_a.sig == fn_ptr_b.sig && fn_ptr_a.num_binders == fn_ptr_b.num_binders =>

+ {

+ zip_substs(self, None, &fn_ptr_a.substitution.0, &fn_ptr_b.substitution.0)?

+ }

+ (TyKind::Error, TyKind::Error) => (),

+ (TyKind::Error, _) | (_, TyKind::Error) => return Err(chalk_ir::NoSolution),

+ _ => (),

+ }

+

+ Ok(())

+ }

+

+ fn zip_lifetimes(&mut self, _: Variance, _: &Lifetime, _: &Lifetime) -> chalk_ir::Fallible<()> {

+ Ok(())

+ }

+

+ fn zip_consts(&mut self, _: Variance, _: &Const, _: &Const) -> chalk_ir::Fallible<()> {

+ Ok(())

+ }

+

+ fn zip_binders<T>(

+ &mut self,

+ variance: Variance,

+ a: &Binders<T>,

+ b: &Binders<T>,

+ ) -> chalk_ir::Fallible<()>

+ where

+ T: Clone

+ + HasInterner<Interner = Interner>

+ + chalk_ir::zip::Zip<Interner>

+ + TypeFoldable<Interner>,

+ {

+ chalk_ir::zip::Zip::zip_with(self, variance, a.skip_binders(), b.skip_binders())

+ }

+

+ fn interner(&self) -> Interner {

+ Interner

+ }

+

+ fn unification_database(&self) -> &dyn chalk_ir::UnificationDatabase<Interner> {

+ &self.0

+ }

+}

+ Statement::Item => (),

+ &Expr::Become { expr } => {

+ self.consume_expr(expr);

+ }

+ &Expr::Become { expr } => self.infer_expr_become(expr),

+ fn infer_expr_become(&mut self, expr: ExprId) -> Ty {

+ match &self.return_coercion {

+ Some(return_coercion) => {

+ let ret_ty = return_coercion.expected_ty();

+

+ let call_expr_ty =

+ self.infer_expr_inner(expr, &Expectation::HasType(ret_ty.clone()));

+

+ // NB: this should *not* coerce.

+ // tail calls don't support any coercions except lifetimes ones (like `&'static u8 -> &'a u8`).

+ self.unify(&call_expr_ty, &ret_ty);

+ }

+ None => {

+ // FIXME: diagnose `become` outside of functions

+ self.infer_expr_no_expect(expr);

+ }

+ }

+

+ self.result.standard_types.never.clone()

+ }

+

+ Statement::Item => (),

+ Statement::Item => (),

+ Expr::Become { expr } => {

+ self.infer_mut_expr(*expr, Mutability::Not);

+ }

+/// Check if types unify.

+///

+/// Note that we consider placeholder types to unify with everything.

+/// This means that there may be some unresolved goals that actually set bounds for the placeholder

+/// type for the types to unify. For example `Option<T>` and `Option<U>` unify although there is

+/// unresolved goal `T = U`.

+/// Check if types unify eagerly making sure there are no unresolved goals.

+///

+/// This means that placeholder types are not considered to unify if there are any bounds set on

+/// them. For example `Option<T>` and `Option<U>` do not unify as we cannot show that `T = U`

+pub fn could_unify_deeply(

+ db: &dyn HirDatabase,

+ env: Arc<TraitEnvironment>,

+ tys: &Canonical<(Ty, Ty)>,

+) -> bool {

+ let mut table = InferenceTable::new(db, env);

+ let vars = make_substitutions(tys, &mut table);

+ let ty1_with_vars = vars.apply(tys.value.0.clone(), Interner);

+ let ty2_with_vars = vars.apply(tys.value.1.clone(), Interner);

+ let ty1_with_vars = table.normalize_associated_types_in(ty1_with_vars);

+ let ty2_with_vars = table.normalize_associated_types_in(ty2_with_vars);

+ table.resolve_obligations_as_possible();

+ table.propagate_diverging_flag();

+ let ty1_with_vars = table.resolve_completely(ty1_with_vars);

+ let ty2_with_vars = table.resolve_completely(ty2_with_vars);

+ table.unify_deeply(&ty1_with_vars, &ty2_with_vars)

+}

+

+ let vars = make_substitutions(tys, &mut table);

+fn make_substitutions(

+ tys: &chalk_ir::Canonical<(chalk_ir::Ty<Interner>, chalk_ir::Ty<Interner>)>,

+ table: &mut InferenceTable<'_>,

+) -> chalk_ir::Substitution<Interner> {

+ Substitution::from_iter(

+ Interner,

+ tys.binders.iter(Interner).map(|it| match &it.kind {

+ chalk_ir::VariableKind::Ty(_) => table.new_type_var().cast(Interner),

+ // FIXME: maybe wrong?

+ chalk_ir::VariableKind::Lifetime => table.new_type_var().cast(Interner),

+ chalk_ir::VariableKind::Const(ty) => table.new_const_var(ty.clone()).cast(Interner),

+ }),

+ )

+}

+

+ /// Unify two relatable values (e.g. `Ty`) and check whether trait goals which arise from that could be fulfilled

+ pub(crate) fn unify_deeply<T: ?Sized + Zip<Interner>>(&mut self, ty1: &T, ty2: &T) -> bool {

+ let result = match self.try_unify(ty1, ty2) {

+ Ok(r) => r,

+ Err(_) => return false,

+ };

+ result.goals.iter().all(|goal| {

+ let canonicalized = self.canonicalize(goal.clone());

+ self.try_resolve_obligation(&canonicalized).is_some()

+ })

+ }

+

+ let solution = self.try_resolve_obligation(&canonicalized);

+ if matches!(solution, Some(Solution::Ambig(_))) {

+ ) -> Option<chalk_solve::Solution<Interner>> {

+ match &solution {

+ binders: canonical_subst.binders.clone(),

+ value: canonical_subst.value.subst.clone(),

+ canonicalized.apply_solution(self, substs.clone());

+ solution

+ match db.data_layout(krate) {

+ Ok(it) => match TargetDataLayout::parse_from_llvm_datalayout_string(&it) {

+ Err(e) => Err(e),

+use project_model::target_data_layout::RustcDataLayoutConfig;

+ project_model::target_data_layout::get(

+ RustcDataLayoutConfig::Rustc(None),

+ None,

+ &FxHashMap::default(),

+ )

+ .unwrap()

+ "//- target_data_layout: {target_data_layout}\n{minicore}//- /main.rs crate:test\n{ra_fixture}",

+ "//- target_data_layout: {target_data_layout}\n{minicore}//- /main.rs crate:test\nfn main(){{let goal = {{{ra_fixture}}};}}",

+ could_coerce, could_unify, could_unify_deeply, Adjust, Adjustment, AutoBorrow, BindingMode,

+ InferenceDiagnostic, InferenceResult, OverloadedDeref, PointerCast,

+use rustc_hash::FxHashMap;

+ ClosureId, Interner, Substitution, Ty, TyExt, TypeFlags,

+pub struct PartiallyMoved {

+ pub ty: Ty,

+ pub span: MirSpan,

+ pub local: LocalId,

+}

+

+#[derive(Debug, Clone, PartialEq, Eq)]

+pub struct BorrowRegion {

+ pub local: LocalId,

+ pub kind: BorrowKind,

+ pub places: Vec<MirSpan>,

+}

+

+#[derive(Debug, Clone, PartialEq, Eq)]

+ pub partially_moved: Vec<PartiallyMoved>,

+ pub borrow_regions: Vec<BorrowRegion>,

+ partially_moved: partially_moved(db, &body),

+ borrow_regions: borrow_regions(db, &body),

+fn make_fetch_closure_field(

+ db: &dyn HirDatabase,

+) -> impl FnOnce(ClosureId, &Substitution, usize) -> Ty + '_ {

+ |c: ClosureId, subst: &Substitution, f: usize| {

+ let InternedClosure(def, _) = db.lookup_intern_closure(c.into());

+ let infer = db.infer(def);

+ let (captures, _) = infer.closure_info(&c);

+ let parent_subst = ClosureSubst(subst).parent_subst();

+ captures.get(f).expect("broken closure field").ty.clone().substitute(Interner, parent_subst)

+ }

+}

+

+ make_fetch_closure_field(db),

+fn partially_moved(db: &dyn HirDatabase, body: &MirBody) -> Vec<PartiallyMoved> {

+ let mut result = vec![];

+ let mut for_operand = |op: &Operand, span: MirSpan| match op {

+ Operand::Copy(p) | Operand::Move(p) => {

+ let mut ty: Ty = body.locals[p.local].ty.clone();

+ for proj in p.projection.lookup(&body.projection_store) {

+ ty = proj.projected_ty(

+ ty,

+ db,

+ make_fetch_closure_field(db),

+ body.owner.module(db.upcast()).krate(),

+ );

+ }

+ if !ty.clone().is_copy(db, body.owner)

+ && !ty.data(Interner).flags.intersects(TypeFlags::HAS_ERROR)

+ {

+ result.push(PartiallyMoved { span, ty, local: p.local });

+ }

+ }

+ Operand::Constant(_) | Operand::Static(_) => (),

+ };

+ for (_, block) in body.basic_blocks.iter() {

+ db.unwind_if_cancelled();

+ for statement in &block.statements {

+ match &statement.kind {

+ StatementKind::Assign(_, r) => match r {

+ Rvalue::ShallowInitBoxWithAlloc(_) => (),

+ Rvalue::ShallowInitBox(o, _)

+ | Rvalue::UnaryOp(_, o)

+ | Rvalue::Cast(_, o, _)

+ | Rvalue::Repeat(o, _)

+ | Rvalue::Use(o) => for_operand(o, statement.span),

+ Rvalue::CopyForDeref(_)

+ | Rvalue::Discriminant(_)

+ | Rvalue::Len(_)

+ | Rvalue::Ref(_, _) => (),

+ Rvalue::CheckedBinaryOp(_, o1, o2) => {

+ for_operand(o1, statement.span);

+ for_operand(o2, statement.span);

+ }

+ Rvalue::Aggregate(_, ops) => {

+ for op in ops.iter() {

+ for_operand(op, statement.span);

+ }

+ }

+ },

+ StatementKind::FakeRead(_)

+ | StatementKind::Deinit(_)

+ | StatementKind::StorageLive(_)

+ | StatementKind::StorageDead(_)

+ | StatementKind::Nop => (),

+ }

+ }

+ match &block.terminator {

+ Some(terminator) => match &terminator.kind {

+ TerminatorKind::SwitchInt { discr, .. } => for_operand(discr, terminator.span),

+ TerminatorKind::FalseEdge { .. }

+ | TerminatorKind::FalseUnwind { .. }

+ | TerminatorKind::Goto { .. }

+ | TerminatorKind::UnwindResume

+ | TerminatorKind::CoroutineDrop

+ | TerminatorKind::Abort

+ | TerminatorKind::Return

+ | TerminatorKind::Unreachable

+ | TerminatorKind::Drop { .. } => (),

+ TerminatorKind::DropAndReplace { value, .. } => {

+ for_operand(value, terminator.span);

+ }

+ TerminatorKind::Call { func, args, .. } => {

+ for_operand(func, terminator.span);

+ args.iter().for_each(|it| for_operand(it, terminator.span));

+ }

+ TerminatorKind::Assert { cond, .. } => {

+ for_operand(cond, terminator.span);

+ }

+ TerminatorKind::Yield { value, .. } => {

+ for_operand(value, terminator.span);

+ }

+ },

+ None => (),

+ }

+ }

+ result.shrink_to_fit();

+ result

+}

+

+fn borrow_regions(db: &dyn HirDatabase, body: &MirBody) -> Vec<BorrowRegion> {

+ let mut borrows = FxHashMap::default();

+ for (_, block) in body.basic_blocks.iter() {

+ db.unwind_if_cancelled();

+ for statement in &block.statements {

+ if let StatementKind::Assign(_, Rvalue::Ref(kind, p)) = &statement.kind {

+ borrows

+ .entry(p.local)

+ .and_modify(|it: &mut BorrowRegion| {

+ it.places.push(statement.span);

+ })

+ .or_insert_with(|| BorrowRegion {

+ local: p.local,

+ kind: *kind,

+ places: vec![statement.span],

+ });

+ }

+ }

+ match &block.terminator {

+ Some(terminator) => match &terminator.kind {

+ TerminatorKind::FalseEdge { .. }

+ | TerminatorKind::FalseUnwind { .. }

+ | TerminatorKind::Goto { .. }

+ | TerminatorKind::UnwindResume

+ | TerminatorKind::CoroutineDrop

+ | TerminatorKind::Abort

+ | TerminatorKind::Return

+ | TerminatorKind::Unreachable

+ | TerminatorKind::Drop { .. } => (),

+ TerminatorKind::DropAndReplace { .. } => {}

+ TerminatorKind::Call { .. } => {}

+ _ => (),

+ },

+ None => (),

+ }

+ }

+

+ borrows.into_values().collect()

+}

+

+ make_fetch_closure_field(db),

+ Expr::Become { .. } => not_supported!("tail-calls"),

+ Expr::Underscore => Ok(Some(current)),

+ hir_def::hir::Statement::Item => (),

+use crate::tests::check_no_mismatches;

+

+

+#[test]

+fn no_mismatches_on_atpit() {

+ check_no_mismatches(

+ r#"

+//- minicore: option, sized

+#![feature(impl_trait_in_assoc_type)]

+

+trait WrappedAssoc {

+ type Assoc;

+ fn do_thing(&self) -> Option<Self::Assoc>;

+}

+

+struct Foo;

+impl WrappedAssoc for Foo {

+ type Assoc = impl Sized;

+

+ fn do_thing(&self) -> Option<Self::Assoc> {

+ Some(())

+ }

+}

+"#,

+ );

+ check_no_mismatches(

+ r#"

+//- minicore: option, sized

+#![feature(impl_trait_in_assoc_type)]

+

+trait Trait {

+ type Assoc;

+ const DEFINE: Option<Self::Assoc>;

+}

+

+impl Trait for () {

+ type Assoc = impl Sized;

+ const DEFINE: Option<Self::Assoc> = Option::Some(());

+}

+"#,

+ );

+}

+pub mod term_search;

+ // FIXME: Find better API to also handle const generics

+ pub fn ty_with_args(&self, db: &dyn HirDatabase, generics: impl Iterator<Item = Type>) -> Type {

+ let var_id = self.parent.into();

+ let def_id: AdtId = match self.parent {

+ VariantDef::Struct(it) => it.id.into(),

+ VariantDef::Union(it) => it.id.into(),

+ VariantDef::Variant(it) => it.parent_enum(db).id.into(),

+ };

+ let mut generics = generics.map(|it| it.ty.clone());

+ let substs = TyBuilder::subst_for_def(db, def_id, None)

+ .fill(|x| match x {

+ ParamKind::Type => {

+ generics.next().unwrap_or_else(|| TyKind::Error.intern(Interner)).cast(Interner)

+ }

+ ParamKind::Const(ty) => unknown_const_as_generic(ty.clone()),

+ })

+ .build();

+ let ty = db.field_types(var_id)[self.id].clone().substitute(Interner, &substs);

+ Type::new(db, var_id, ty)

+ }

+

+

+ pub fn is_unstable(self, db: &dyn HirDatabase) -> bool {

+ db.attrs(self.id.into()).is_unstable()

+ }

+

+ pub fn is_unstable(self, db: &dyn HirDatabase) -> bool {

+ db.attrs(self.id.into()).is_unstable()

+ }

+

+ pub fn is_unstable(self, db: &dyn HirDatabase) -> bool {

+ db.attrs(self.id.into()).is_unstable()

+ }

+

+ pub fn is_unstable(self, db: &dyn HirDatabase) -> bool {

+ db.attrs(self.id.into()).is_unstable()

+ }

+ pub fn ty_with_args(self, db: &dyn HirDatabase, args: impl Iterator<Item = Type>) -> Type {

+ let mut it = args.map(|t| t.ty.clone());

+ // FIXME: Find better API to also handle const generics

+ pub fn ret_type_with_args(

+ self,

+ db: &dyn HirDatabase,

+ generics: impl Iterator<Item = Type>,

+ ) -> Type {

+ let resolver = self.id.resolver(db.upcast());

+ let parent_id: Option<GenericDefId> = match self.id.lookup(db.upcast()).container {

+ ItemContainerId::ImplId(it) => Some(it.into()),

+ ItemContainerId::TraitId(it) => Some(it.into()),

+ ItemContainerId::ModuleId(_) | ItemContainerId::ExternBlockId(_) => None,

+ };

+ let mut generics = generics.map(|it| it.ty.clone());

+ let mut filler = |x: &_| match x {

+ ParamKind::Type => {

+ generics.next().unwrap_or_else(|| TyKind::Error.intern(Interner)).cast(Interner)

+ }

+ ParamKind::Const(ty) => unknown_const_as_generic(ty.clone()),

+ };

+

+ let parent_substs =

+ parent_id.map(|id| TyBuilder::subst_for_def(db, id, None).fill(&mut filler).build());

+ let substs = TyBuilder::subst_for_def(db, self.id, parent_substs).fill(&mut filler).build();

+

+ let callable_sig = db.callable_item_signature(self.id.into()).substitute(Interner, &substs);

+ let ty = callable_sig.ret().clone();

+ Type::new_with_resolver_inner(db, &resolver, ty)

+ }

+

+ // FIXME: Find better API to also handle const generics

+ pub fn params_without_self_with_args(

+ self,

+ db: &dyn HirDatabase,

+ generics: impl Iterator<Item = Type>,

+ ) -> Vec<Param> {

+ let environment = db.trait_environment(self.id.into());

+ let parent_id: Option<GenericDefId> = match self.id.lookup(db.upcast()).container {

+ ItemContainerId::ImplId(it) => Some(it.into()),

+ ItemContainerId::TraitId(it) => Some(it.into()),

+ ItemContainerId::ModuleId(_) | ItemContainerId::ExternBlockId(_) => None,

+ };

+ let mut generics = generics.map(|it| it.ty.clone());

+ let parent_substs = parent_id.map(|id| {

+ TyBuilder::subst_for_def(db, id, None)

+ .fill(|x| match x {

+ ParamKind::Type => generics

+ .next()

+ .unwrap_or_else(|| TyKind::Error.intern(Interner))

+ .cast(Interner),

+ ParamKind::Const(ty) => unknown_const_as_generic(ty.clone()),

+ })

+ .build()

+ });

+

+ let substs = TyBuilder::subst_for_def(db, self.id, parent_substs)

+ .fill(|_| {

+ let ty = generics.next().unwrap_or_else(|| TyKind::Error.intern(Interner));

+ GenericArg::new(Interner, GenericArgData::Ty(ty))

+ })

+ .build();

+ let callable_sig = db.callable_item_signature(self.id.into()).substitute(Interner, &substs);

+ let skip = if db.function_data(self.id).has_self_param() { 1 } else { 0 };

+ callable_sig

+ .params()

+ .iter()

+ .enumerate()

+ .skip(skip)

+ .map(|(idx, ty)| {

+ let ty = Type { env: environment.clone(), ty: ty.clone() };

+ Param { func: self, ty, idx }

+ })

+ .collect()

+ }

+

+ /// Is this function marked as unstable with `#[feature]` attribute?

+ pub fn is_unstable(self, db: &dyn HirDatabase) -> bool {

+ db.function_data(self.id).attrs.is_unstable()

+ }

+

+

+ // FIXME: Find better API to also handle const generics

+ pub fn ty_with_args(&self, db: &dyn HirDatabase, generics: impl Iterator<Item = Type>) -> Type {

+ let parent_id: GenericDefId = match self.func.lookup(db.upcast()).container {

+ ItemContainerId::ImplId(it) => it.into(),

+ ItemContainerId::TraitId(it) => it.into(),

+ ItemContainerId::ModuleId(_) | ItemContainerId::ExternBlockId(_) => {

+ panic!("Never get here")

+ }

+ };

+

+ let mut generics = generics.map(|it| it.ty.clone());

+ let mut filler = |x: &_| match x {

+ ParamKind::Type => {

+ generics.next().unwrap_or_else(|| TyKind::Error.intern(Interner)).cast(Interner)

+ }

+ ParamKind::Const(ty) => unknown_const_as_generic(ty.clone()),

+ };

+

+ let parent_substs = TyBuilder::subst_for_def(db, parent_id, None).fill(&mut filler).build();

+ let substs =

+ TyBuilder::subst_for_def(db, self.func, Some(parent_substs)).fill(&mut filler).build();

+ let callable_sig =

+ db.callable_item_signature(self.func.into()).substitute(Interner, &substs);

+ let environment = db.trait_environment(self.func.into());

+ let ty = callable_sig.params()[0].clone();

+ Type { env: environment, ty }

+ }

+ pub fn type_or_const_params(self, db: &dyn HirDatabase) -> Vec<TypeOrConstParam> {

+ GenericArgData::Ty(it) if *it.kind(Interner) != TyKind::Error => {

+

+ pub fn is_unstable(self, db: &dyn HirDatabase) -> bool {

+ db.attrs(GenericParamId::from(self.id).into()).is_unstable()

+ }

+

+ pub fn as_type_param(self, db: &dyn HirDatabase) -> Option<TypeParam> {

+ let params = db.generic_params(self.id.parent);

+ match &params.type_or_consts[self.id.local_id] {

+ hir_def::generics::TypeOrConstParamData::TypeParamData(_) => {

+ Some(TypeParam { id: TypeParamId::from_unchecked(self.id) })

+ }

+ hir_def::generics::TypeOrConstParamData::ConstParamData(_) => None,

+ }

+ }

+

+ pub fn as_const_param(self, db: &dyn HirDatabase) -> Option<ConstParam> {

+ let params = db.generic_params(self.id.parent);

+ match &params.type_or_consts[self.id.local_id] {

+ hir_def::generics::TypeOrConstParamData::TypeParamData(_) => None,

+ hir_def::generics::TypeOrConstParamData::ConstParamData(_) => {

+ Some(ConstParam { id: ConstParamId::from_unchecked(self.id) })

+ }

+ }

+ }

+

+#[derive(Clone, PartialEq, Eq, Debug, Hash)]

+ pub fn contains_reference(&self, db: &dyn HirDatabase) -> bool {

+ return go(db, self.env.krate, &self.ty);

+

+ fn go(db: &dyn HirDatabase, krate: CrateId, ty: &Ty) -> bool {

+ match ty.kind(Interner) {

+ // Reference itself

+ TyKind::Ref(_, _, _) => true,

+

+ // For non-phantom_data adts we check variants/fields as well as generic parameters

+ TyKind::Adt(adt_id, substitution)

+ if !db.struct_datum(krate, *adt_id).flags.phantom_data =>

+ {

+ let adt_datum = &db.struct_datum(krate, *adt_id);

+ let adt_datum_bound =

+ adt_datum.binders.clone().substitute(Interner, substitution);

+ adt_datum_bound

+ .variants

+ .into_iter()

+ .flat_map(|variant| variant.fields.into_iter())

+ .any(|ty| go(db, krate, &ty))

+ || substitution

+ .iter(Interner)

+ .filter_map(|x| x.ty(Interner))

+ .any(|ty| go(db, krate, ty))

+ }

+ // And for `PhantomData<T>`, we check `T`.

+ TyKind::Adt(_, substitution)

+ | TyKind::Tuple(_, substitution)

+ | TyKind::OpaqueType(_, substitution)

+ | TyKind::AssociatedType(_, substitution)

+ | TyKind::FnDef(_, substitution) => substitution

+ .iter(Interner)

+ .filter_map(|x| x.ty(Interner))

+ .any(|ty| go(db, krate, ty)),

+

+ // For `[T]` or `*T` we check `T`

+ TyKind::Array(ty, _) | TyKind::Slice(ty) | TyKind::Raw(_, ty) => go(db, krate, ty),

+

+ // Consider everything else as not reference

+ _ => false,

+ }

+ }

+ }

+

+ // FIXME: Find better API that also handles const generics

+ ParamKind::Type => {

+ it.next().unwrap_or_else(|| TyKind::Error.intern(Interner)).cast(Interner)

+ }

+ /// Check if type unifies with another type.

+ ///

+ /// Note that we consider placeholder types to unify with everything.

+ /// For example `Option<T>` and `Option<U>` unify although there is unresolved goal `T = U`.

+ /// Check if type unifies with another type eagerly making sure there are no unresolved goals.

+ ///

+ /// This means that placeholder types are not considered to unify if there are any bounds set on

+ /// them. For example `Option<T>` and `Option<U>` do not unify as we cannot show that `T = U`

+ pub fn could_unify_with_deeply(&self, db: &dyn HirDatabase, other: &Type) -> bool {

+ let tys = hir_ty::replace_errors_with_variables(&(self.ty.clone(), other.ty.clone()));

+ hir_ty::could_unify_deeply(db, self.env.clone(), &tys)

+ }

+

+//! Term search

+

+use hir_def::type_ref::Mutability;

+use hir_ty::db::HirDatabase;

+use itertools::Itertools;

+use rustc_hash::{FxHashMap, FxHashSet};

+

+use crate::{ModuleDef, ScopeDef, Semantics, SemanticsScope, Type};

+

+mod expr;

+pub use expr::Expr;

+

+mod tactics;

+

+/// Key for lookup table to query new types reached.

+#[derive(Debug, Hash, PartialEq, Eq)]

+enum NewTypesKey {

+ ImplMethod,

+ StructProjection,

+}

+

+/// Helper enum to squash big number of alternative trees into `Many` variant as there is too many

+/// to take into account.

+#[derive(Debug)]

+enum AlternativeExprs {

+ /// There are few trees, so we keep track of them all

+ Few(FxHashSet<Expr>),

+ /// There are too many trees to keep track of

+ Many,

+}

+

+impl AlternativeExprs {

+ /// Construct alternative trees

+ ///

+ /// # Arguments

+ /// `threshold` - threshold value for many trees (more than that is many)

+ /// `exprs` - expressions iterator

+ fn new(threshold: usize, exprs: impl Iterator<Item = Expr>) -> AlternativeExprs {

+ let mut it = AlternativeExprs::Few(Default::default());

+ it.extend_with_threshold(threshold, exprs);

+ it

+ }

+

+ /// Get type trees stored in alternative trees (or `Expr::Many` in case of many)

+ ///

+ /// # Arguments

+ /// `ty` - Type of expressions queried (this is used to give type to `Expr::Many`)

+ fn exprs(&self, ty: &Type) -> Vec<Expr> {

+ match self {

+ AlternativeExprs::Few(exprs) => exprs.iter().cloned().collect(),

+ AlternativeExprs::Many => vec![Expr::Many(ty.clone())],

+ }

+ }

+

+ /// Extend alternative expressions

+ ///

+ /// # Arguments

+ /// `threshold` - threshold value for many trees (more than that is many)

+ /// `exprs` - expressions iterator

+ fn extend_with_threshold(&mut self, threshold: usize, exprs: impl Iterator<Item = Expr>) {

+ match self {

+ AlternativeExprs::Few(tts) => {

+ for it in exprs {

+ if tts.len() > threshold {

+ *self = AlternativeExprs::Many;

+ break;

+ }

+

+ tts.insert(it);

+ }

+ }

+ AlternativeExprs::Many => (),

+ }

+ }

+}

+

+/// # Lookup table for term search

+///

+/// Lookup table keeps all the state during term search.

+/// This means it knows what types and how are reachable.

+///

+/// The secondary functionality for lookup table is to keep track of new types reached since last

+/// iteration as well as keeping track of which `ScopeDef` items have been used.

+/// Both of them are to speed up the term search by leaving out types / ScopeDefs that likely do

+/// not produce any new results.

+#[derive(Default, Debug)]

+struct LookupTable {

+ /// All the `Expr`s in "value" produce the type of "key"

+ data: FxHashMap<Type, AlternativeExprs>,

+ /// New types reached since last query by the `NewTypesKey`

+ new_types: FxHashMap<NewTypesKey, Vec<Type>>,

+ /// ScopeDefs that are not interesting any more

+ exhausted_scopedefs: FxHashSet<ScopeDef>,

+ /// ScopeDefs that were used in current round

+ round_scopedef_hits: FxHashSet<ScopeDef>,

+ /// Amount of rounds since scopedef was first used.

+ rounds_since_sopedef_hit: FxHashMap<ScopeDef, u32>,

+ /// Types queried but not present

+ types_wishlist: FxHashSet<Type>,

+ /// Threshold to squash trees to `Many`

+ many_threshold: usize,

+}

+

+impl LookupTable {

+ /// Initialize lookup table

+ fn new(many_threshold: usize) -> Self {

+ let mut res = Self { many_threshold, ..Default::default() };

+ res.new_types.insert(NewTypesKey::ImplMethod, Vec::new());

+ res.new_types.insert(NewTypesKey::StructProjection, Vec::new());

+ res

+ }

+

+ /// Find all `Expr`s that unify with the `ty`

+ fn find(&self, db: &dyn HirDatabase, ty: &Type) -> Option<Vec<Expr>> {

+ self.data

+ .iter()

+ .find(|(t, _)| t.could_unify_with_deeply(db, ty))

+ .map(|(t, tts)| tts.exprs(t))

+ }

+

+ /// Same as find but automatically creates shared reference of types in the lookup

+ ///

+ /// For example if we have type `i32` in data and we query for `&i32` it map all the type

+ /// trees we have for `i32` with `Expr::Reference` and returns them.

+ fn find_autoref(&self, db: &dyn HirDatabase, ty: &Type) -> Option<Vec<Expr>> {

+ self.data

+ .iter()

+ .find(|(t, _)| t.could_unify_with_deeply(db, ty))

+ .map(|(t, it)| it.exprs(t))

+ .or_else(|| {

+ self.data

+ .iter()

+ .find(|(t, _)| {

+ Type::reference(t, Mutability::Shared).could_unify_with_deeply(db, ty)

+ })

+ .map(|(t, it)| {

+ it.exprs(t)

+ .into_iter()

+ .map(|expr| Expr::Reference(Box::new(expr)))

+ .collect()

+ })

+ })

+ }

+

+ /// Insert new type trees for type

+ ///

+ /// Note that the types have to be the same, unification is not enough as unification is not

+ /// transitive. For example Vec<i32> and FxHashSet<i32> both unify with Iterator<Item = i32>,

+ /// but they clearly do not unify themselves.

+ fn insert(&mut self, ty: Type, exprs: impl Iterator<Item = Expr>) {

+ match self.data.get_mut(&ty) {

+ Some(it) => it.extend_with_threshold(self.many_threshold, exprs),

+ None => {

+ self.data.insert(ty.clone(), AlternativeExprs::new(self.many_threshold, exprs));

+ for it in self.new_types.values_mut() {

+ it.push(ty.clone());

+ }

+ }

+ }

+ }

+

+ /// Iterate all the reachable types

+ fn iter_types(&self) -> impl Iterator<Item = Type> + '_ {

+ self.data.keys().cloned()

+ }

+

+ /// Query new types reached since last query by key

+ ///

+ /// Create new key if you wish to query it to avoid conflicting with existing queries.

+ fn new_types(&mut self, key: NewTypesKey) -> Vec<Type> {

+ match self.new_types.get_mut(&key) {

+ Some(it) => std::mem::take(it),

+ None => Vec::new(),

+ }

+ }

+

+ /// Mark `ScopeDef` as exhausted meaning it is not interesting for us any more

+ fn mark_exhausted(&mut self, def: ScopeDef) {

+ self.exhausted_scopedefs.insert(def);

+ }

+

+ /// Mark `ScopeDef` as used meaning we managed to produce something useful from it

+ fn mark_fulfilled(&mut self, def: ScopeDef) {

+ self.round_scopedef_hits.insert(def);

+ }

+

+ /// Start new round (meant to be called at the beginning of iteration in `term_search`)

+ ///

+ /// This functions marks some `ScopeDef`s as exhausted if there have been

+ /// `MAX_ROUNDS_AFTER_HIT` rounds after first using a `ScopeDef`.

+ fn new_round(&mut self) {

+ for def in &self.round_scopedef_hits {

+ let hits =

+ self.rounds_since_sopedef_hit.entry(*def).and_modify(|n| *n += 1).or_insert(0);

+ const MAX_ROUNDS_AFTER_HIT: u32 = 2;

+ if *hits > MAX_ROUNDS_AFTER_HIT {

+ self.exhausted_scopedefs.insert(*def);

+ }

+ }

+ self.round_scopedef_hits.clear();

+ }

+

+ /// Get exhausted `ScopeDef`s

+ fn exhausted_scopedefs(&self) -> &FxHashSet<ScopeDef> {

+ &self.exhausted_scopedefs

+ }

+

+ /// Types queried but not found

+ fn take_types_wishlist(&mut self) -> FxHashSet<Type> {

+ std::mem::take(&mut self.types_wishlist)

+ }

+}

+

+/// Context for the `term_search` function

+#[derive(Debug)]

+pub struct TermSearchCtx<'a, DB: HirDatabase> {

+ /// Semantics for the program

+ pub sema: &'a Semantics<'a, DB>,

+ /// Semantic scope, captures context for the term search

+ pub scope: &'a SemanticsScope<'a>,

+ /// Target / expected output type

+ pub goal: Type,

+ /// Configuration for term search

+ pub config: TermSearchConfig,

+}

+

+/// Configuration options for the term search

+#[derive(Debug, Clone, Copy)]

+pub struct TermSearchConfig {

+ /// Enable borrow checking, this guarantees the outputs of the `term_search` to borrow-check

+ pub enable_borrowcheck: bool,

+ /// Indicate when to squash multiple trees to `Many` as there are too many to keep track

+ pub many_alternatives_threshold: usize,

+ /// Depth of the search eg. number of cycles to run

+ pub depth: usize,

+}

+

+impl Default for TermSearchConfig {

+ fn default() -> Self {

+ Self { enable_borrowcheck: true, many_alternatives_threshold: 1, depth: 6 }

+ }

+}

+

+/// # Term search

+///

+/// Search for terms (expressions) that unify with the `goal` type.

+///

+/// # Arguments

+/// * `ctx` - Context for term search

+///

+/// Internally this function uses Breadth First Search to find path to `goal` type.

+/// The general idea is following:

+/// 1. Populate lookup (frontier for BFS) from values (local variables, statics, constants, etc)

+/// as well as from well knows values (such as `true/false` and `()`)

+/// 2. Iteratively expand the frontier (or contents of the lookup) by trying different type

+/// transformation tactics. For example functions take as from set of types (arguments) to some

+/// type (return type). Other transformations include methods on type, type constructors and

+/// projections to struct fields (field access).

+/// 3. Once we manage to find path to type we are interested in we continue for single round to see

+/// if we can find more paths that take us to the `goal` type.

+/// 4. Return all the paths (type trees) that take us to the `goal` type.

+///

+/// Note that there are usually more ways we can get to the `goal` type but some are discarded to

+/// reduce the memory consumption. It is also unlikely anyone is willing ti browse through

+/// thousands of possible responses so we currently take first 10 from every tactic.

+pub fn term_search<DB: HirDatabase>(ctx: &TermSearchCtx<'_, DB>) -> Vec<Expr> {

+ let module = ctx.scope.module();

+ let mut defs = FxHashSet::default();

+ defs.insert(ScopeDef::ModuleDef(ModuleDef::Module(module)));

+

+ ctx.scope.process_all_names(&mut |_, def| {

+ defs.insert(def);

+ });

+

+ let mut lookup = LookupTable::new(ctx.config.many_alternatives_threshold);

+

+ // Try trivial tactic first, also populates lookup table

+ let mut solutions: Vec<Expr> = tactics::trivial(ctx, &defs, &mut lookup).collect();

+ // Use well known types tactic before iterations as it does not depend on other tactics

+ solutions.extend(tactics::famous_types(ctx, &defs, &mut lookup));

+

+ for _ in 0..ctx.config.depth {

+ lookup.new_round();

+

+ solutions.extend(tactics::type_constructor(ctx, &defs, &mut lookup));

+ solutions.extend(tactics::free_function(ctx, &defs, &mut lookup));

+ solutions.extend(tactics::impl_method(ctx, &defs, &mut lookup));

+ solutions.extend(tactics::struct_projection(ctx, &defs, &mut lookup));

+ solutions.extend(tactics::impl_static_method(ctx, &defs, &mut lookup));

+

+ // Discard not interesting `ScopeDef`s for speedup

+ for def in lookup.exhausted_scopedefs() {

+ defs.remove(def);

+ }

+ }

+

+ solutions.into_iter().filter(|it| !it.is_many()).unique().collect()

+}

+//! Type tree for term search

+

+use hir_def::find_path::PrefixKind;

+use hir_expand::mod_path::ModPath;

+use hir_ty::{

+ db::HirDatabase,

+ display::{DisplaySourceCodeError, HirDisplay},

+};

+use itertools::Itertools;

+

+use crate::{

+ Adt, AsAssocItem, Const, ConstParam, Field, Function, GenericDef, Local, ModuleDef,

+ SemanticsScope, Static, Struct, StructKind, Trait, Type, Variant,

+};

+

+/// Helper function to get path to `ModuleDef`

+fn mod_item_path(

+ sema_scope: &SemanticsScope<'_>,

+ def: &ModuleDef,

+ prefer_no_std: bool,

+ prefer_prelude: bool,

+) -> Option<ModPath> {

+ let db = sema_scope.db;

+ // Account for locals shadowing items from module

+ let name_hit_count = def.name(db).map(|def_name| {

+ let mut name_hit_count = 0;

+ sema_scope.process_all_names(&mut |name, _| {

+ if name == def_name {

+ name_hit_count += 1;

+ }

+ });

+ name_hit_count

+ });

+

+ let m = sema_scope.module();

+ match name_hit_count {

+ Some(0..=1) | None => m.find_use_path(db.upcast(), *def, prefer_no_std, prefer_prelude),

+ Some(_) => m.find_use_path_prefixed(

+ db.upcast(),

+ *def,

+ PrefixKind::ByCrate,

+ prefer_no_std,

+ prefer_prelude,

+ ),

+ }

+}

+

+/// Helper function to get path to `ModuleDef` as string

+fn mod_item_path_str(

+ sema_scope: &SemanticsScope<'_>,

+ def: &ModuleDef,

+ prefer_no_std: bool,

+ prefer_prelude: bool,

+) -> Result<String, DisplaySourceCodeError> {

+ let path = mod_item_path(sema_scope, def, prefer_no_std, prefer_prelude);

+ path.map(|it| it.display(sema_scope.db.upcast()).to_string())

+ .ok_or(DisplaySourceCodeError::PathNotFound)

+}

+

+/// Helper function to get path to `Type`

+fn type_path(

+ sema_scope: &SemanticsScope<'_>,

+ ty: &Type,

+ prefer_no_std: bool,

+ prefer_prelude: bool,

+) -> Result<String, DisplaySourceCodeError> {

+ let db = sema_scope.db;

+ let m = sema_scope.module();

+

+ match ty.as_adt() {

+ Some(adt) => {

+ let ty_name = ty.display_source_code(db, m.id, true)?;

+

+ let mut path =

+ mod_item_path(sema_scope, &ModuleDef::Adt(adt), prefer_no_std, prefer_prelude)

+ .unwrap();

+ path.pop_segment();

+ let path = path.display(db.upcast()).to_string();

+ let res = match path.is_empty() {

+ true => ty_name,

+ false => format!("{path}::{ty_name}"),

+ };

+ Ok(res)

+ }

+ None => ty.display_source_code(db, m.id, true),

+ }

+}

+

+/// Helper function to filter out generic parameters that are default

+fn non_default_generics(db: &dyn HirDatabase, def: GenericDef, generics: &[Type]) -> Vec<Type> {

+ def.type_or_const_params(db)

+ .into_iter()

+ .filter_map(|it| it.as_type_param(db))

+ .zip(generics)

+ .filter(|(tp, arg)| tp.default(db).as_ref() != Some(arg))

+ .map(|(_, arg)| arg.clone())

+ .collect()

+}

+

+/// Type tree shows how can we get from set of types to some type.

+///

+/// Consider the following code as an example

+/// ```

+/// fn foo(x: i32, y: bool) -> Option<i32> { None }

+/// fn bar() {

+/// let a = 1;

+/// let b = true;

+/// let c: Option<i32> = _;

+/// }

+/// ```

+/// If we generate type tree in the place of `_` we get

+/// ```txt

+/// Option<i32>

+/// |

+/// foo(i32, bool)

+/// / \

+/// a: i32 b: bool

+/// ```

+/// So in short it pretty much gives us a way to get type `Option<i32>` using the items we have in

+/// scope.

+#[derive(Debug, Clone, Eq, Hash, PartialEq)]

+pub enum Expr {

+ /// Constant

+ Const(Const),

+ /// Static variable

+ Static(Static),

+ /// Local variable

+ Local(Local),

+ /// Constant generic parameter

+ ConstParam(ConstParam),

+ /// Well known type (such as `true` for bool)

+ FamousType { ty: Type, value: &'static str },

+ /// Function call (does not take self param)

+ Function { func: Function, generics: Vec<Type>, params: Vec<Expr> },

+ /// Method call (has self param)

+ Method { func: Function, generics: Vec<Type>, target: Box<Expr>, params: Vec<Expr> },

+ /// Enum variant construction

+ Variant { variant: Variant, generics: Vec<Type>, params: Vec<Expr> },

+ /// Struct construction

+ Struct { strukt: Struct, generics: Vec<Type>, params: Vec<Expr> },

+ /// Struct field access

+ Field { expr: Box<Expr>, field: Field },

+ /// Passing type as reference (with `&`)

+ Reference(Box<Expr>),

+ /// Indicates possibility of many different options that all evaluate to `ty`

+ Many(Type),

+}

+

+impl Expr {

+ /// Generate source code for type tree.

+ ///

+ /// Note that trait imports are not added to generated code.

+ /// To make sure that the code is valid, callee has to also ensure that all the traits listed

+ /// by `traits_used` method are also imported.

+ pub fn gen_source_code(

+ &self,

+ sema_scope: &SemanticsScope<'_>,

+ many_formatter: &mut dyn FnMut(&Type) -> String,

+ prefer_no_std: bool,

+ prefer_prelude: bool,

+ ) -> Result<String, DisplaySourceCodeError> {

+ let db = sema_scope.db;

+ let mod_item_path_str = |s, def| mod_item_path_str(s, def, prefer_no_std, prefer_prelude);

+ match self {

+ Expr::Const(it) => mod_item_path_str(sema_scope, &ModuleDef::Const(*it)),

+ Expr::Static(it) => mod_item_path_str(sema_scope, &ModuleDef::Static(*it)),

+ Expr::Local(it) => Ok(it.name(db).display(db.upcast()).to_string()),

+ Expr::ConstParam(it) => Ok(it.name(db).display(db.upcast()).to_string()),

+ Expr::FamousType { value, .. } => Ok(value.to_string()),

+ Expr::Function { func, params, .. } => {

+ let args = params

+ .iter()

+ .map(|f| {

+ f.gen_source_code(sema_scope, many_formatter, prefer_no_std, prefer_prelude)

+ })

+ .collect::<Result<Vec<String>, DisplaySourceCodeError>>()?

+ .into_iter()

+ .join(", ");

+

+ match func.as_assoc_item(db).map(|it| it.container(db)) {

+ Some(container) => {

+ let container_name = match container {

+ crate::AssocItemContainer::Trait(trait_) => {

+ mod_item_path_str(sema_scope, &ModuleDef::Trait(trait_))?

+ }

+ crate::AssocItemContainer::Impl(imp) => {

+ let self_ty = imp.self_ty(db);

+ // Should it be guaranteed that `mod_item_path` always exists?

+ match self_ty.as_adt().and_then(|adt| {

+ mod_item_path(

+ sema_scope,

+ &adt.into(),

+ prefer_no_std,

+ prefer_prelude,

+ )

+ }) {

+ Some(path) => path.display(sema_scope.db.upcast()).to_string(),

+ None => self_ty.display(db).to_string(),

+ }

+ }

+ };

+ let fn_name = func.name(db).display(db.upcast()).to_string();

+ Ok(format!("{container_name}::{fn_name}({args})"))

+ }

+ None => {

+ let fn_name = mod_item_path_str(sema_scope, &ModuleDef::Function(*func))?;

+ Ok(format!("{fn_name}({args})"))

+ }

+ }

+ }

+ Expr::Method { func, target, params, .. } => {

+ if target.contains_many_in_illegal_pos() {

+ return Ok(many_formatter(&target.ty(db)));

+ }

+

+ let func_name = func.name(db).display(db.upcast()).to_string();

+ let self_param = func.self_param(db).unwrap();

+ let target = target.gen_source_code(

+ sema_scope,

+ many_formatter,

+ prefer_no_std,

+ prefer_prelude,

+ )?;

+ let args = params

+ .iter()

+ .map(|f| {

+ f.gen_source_code(sema_scope, many_formatter, prefer_no_std, prefer_prelude)

+ })

+ .collect::<Result<Vec<String>, DisplaySourceCodeError>>()?

+ .into_iter()

+ .join(", ");

+

+ match func.as_assoc_item(db).and_then(|it| it.container_or_implemented_trait(db)) {

+ Some(trait_) => {

+ let trait_name = mod_item_path_str(sema_scope, &ModuleDef::Trait(trait_))?;

+ let target = match self_param.access(db) {

+ crate::Access::Shared => format!("&{target}"),

+ crate::Access::Exclusive => format!("&mut {target}"),

+ crate::Access::Owned => target,

+ };

+ let res = match args.is_empty() {

+ true => format!("{trait_name}::{func_name}({target})",),

+ false => format!("{trait_name}::{func_name}({target}, {args})",),

+ };

+ Ok(res)

+ }

+ None => Ok(format!("{target}.{func_name}({args})")),

+ }

+ }

+ Expr::Variant { variant, generics, params } => {

+ let generics = non_default_generics(db, (*variant).into(), generics);

+ let generics_str = match generics.is_empty() {

+ true => String::new(),

+ false => {

+ let generics = generics

+ .iter()

+ .map(|it| type_path(sema_scope, it, prefer_no_std, prefer_prelude))

+ .collect::<Result<Vec<String>, DisplaySourceCodeError>>()?

+ .into_iter()

+ .join(", ");

+ format!("::<{generics}>")

+ }

+ };

+ let inner = match variant.kind(db) {

+ StructKind::Tuple => {

+ let args = params

+ .iter()

+ .map(|f| {

+ f.gen_source_code(

+ sema_scope,

+ many_formatter,

+ prefer_no_std,

+ prefer_prelude,

+ )

+ })

+ .collect::<Result<Vec<String>, DisplaySourceCodeError>>()?

+ .into_iter()

+ .join(", ");

+ format!("{generics_str}({args})")

+ }

+ StructKind::Record => {

+ let fields = variant.fields(db);

+ let args = params

+ .iter()

+ .zip(fields.iter())

+ .map(|(a, f)| {

+ let tmp = format!(

+ "{}: {}",

+ f.name(db).display(db.upcast()),

+ a.gen_source_code(

+ sema_scope,

+ many_formatter,

+ prefer_no_std,

+ prefer_prelude

+ )?

+ );

+ Ok(tmp)

+ })

+ .collect::<Result<Vec<String>, DisplaySourceCodeError>>()?

+ .into_iter()

+ .join(", ");

+ format!("{generics_str}{{ {args} }}")

+ }

+ StructKind::Unit => generics_str,

+ };

+

+ let prefix = mod_item_path_str(sema_scope, &ModuleDef::Variant(*variant))?;

+ Ok(format!("{prefix}{inner}"))

+ }

+ Expr::Struct { strukt, generics, params } => {

+ let generics = non_default_generics(db, (*strukt).into(), generics);

+ let inner = match strukt.kind(db) {

+ StructKind::Tuple => {

+ let args = params

+ .iter()

+ .map(|a| {

+ a.gen_source_code(

+ sema_scope,

+ many_formatter,

+ prefer_no_std,

+ prefer_prelude,

+ )

+ })

+ .collect::<Result<Vec<String>, DisplaySourceCodeError>>()?

+ .into_iter()

+ .join(", ");

+ format!("({args})")

+ }

+ StructKind::Record => {

+ let fields = strukt.fields(db);

+ let args = params

+ .iter()

+ .zip(fields.iter())

+ .map(|(a, f)| {

+ let tmp = format!(

+ "{}: {}",

+ f.name(db).display(db.upcast()),

+ a.gen_source_code(

+ sema_scope,

+ many_formatter,

+ prefer_no_std,

+ prefer_prelude

+ )?

+ );

+ Ok(tmp)

+ })

+ .collect::<Result<Vec<String>, DisplaySourceCodeError>>()?

+ .into_iter()

+ .join(", ");

+ format!(" {{ {args} }}")

+ }

+ StructKind::Unit => match generics.is_empty() {

+ true => String::new(),

+ false => {

+ let generics = generics

+ .iter()

+ .map(|it| type_path(sema_scope, it, prefer_no_std, prefer_prelude))

+ .collect::<Result<Vec<String>, DisplaySourceCodeError>>()?

+ .into_iter()

+ .join(", ");

+ format!("::<{generics}>")

+ }

+ },

+ };

+

+ let prefix = mod_item_path_str(sema_scope, &ModuleDef::Adt(Adt::Struct(*strukt)))?;

+ Ok(format!("{prefix}{inner}"))

+ }

+ Expr::Field { expr, field } => {

+ if expr.contains_many_in_illegal_pos() {

+ return Ok(many_formatter(&expr.ty(db)));

+ }

+

+ let strukt = expr.gen_source_code(

+ sema_scope,

+ many_formatter,

+ prefer_no_std,

+ prefer_prelude,

+ )?;

+ let field = field.name(db).display(db.upcast()).to_string();

+ Ok(format!("{strukt}.{field}"))

+ }

+ Expr::Reference(expr) => {

+ if expr.contains_many_in_illegal_pos() {

+ return Ok(many_formatter(&expr.ty(db)));

+ }

+

+ let inner = expr.gen_source_code(

+ sema_scope,

+ many_formatter,

+ prefer_no_std,

+ prefer_prelude,

+ )?;

+ Ok(format!("&{inner}"))

+ }

+ Expr::Many(ty) => Ok(many_formatter(ty)),

+ }

+ }

+

+ /// Get type of the type tree.

+ ///

+ /// Same as getting the type of root node

+ pub fn ty(&self, db: &dyn HirDatabase) -> Type {

+ match self {

+ Expr::Const(it) => it.ty(db),

+ Expr::Static(it) => it.ty(db),

+ Expr::Local(it) => it.ty(db),

+ Expr::ConstParam(it) => it.ty(db),

+ Expr::FamousType { ty, .. } => ty.clone(),

+ Expr::Function { func, generics, .. } => {

+ func.ret_type_with_args(db, generics.iter().cloned())

+ }

+ Expr::Method { func, generics, target, .. } => func.ret_type_with_args(

+ db,

+ target.ty(db).type_arguments().chain(generics.iter().cloned()),

+ ),

+ Expr::Variant { variant, generics, .. } => {

+ Adt::from(variant.parent_enum(db)).ty_with_args(db, generics.iter().cloned())

+ }

+ Expr::Struct { strukt, generics, .. } => {

+ Adt::from(*strukt).ty_with_args(db, generics.iter().cloned())

+ }

+ Expr::Field { expr, field } => field.ty_with_args(db, expr.ty(db).type_arguments()),

+ Expr::Reference(it) => it.ty(db),

+ Expr::Many(ty) => ty.clone(),

+ }

+ }

+

+ /// List the traits used in type tree

+ pub fn traits_used(&self, db: &dyn HirDatabase) -> Vec<Trait> {

+ let mut res = Vec::new();

+

+ if let Expr::Method { func, params, .. } = self {

+ res.extend(params.iter().flat_map(|it| it.traits_used(db)));

+ if let Some(it) = func.as_assoc_item(db) {

+ if let Some(it) = it.container_or_implemented_trait(db) {

+ res.push(it);

+ }

+ }

+ }

+

+ res

+ }

+

+ /// Check in the tree contains `Expr::Many` variant in illegal place to insert `todo`,

+ /// `unimplemented` or similar macro

+ ///

+ /// Some examples are following

+ /// ```no_compile

+ /// macro!().foo

+ /// macro!().bar()

+ /// &macro!()

+ /// ```

+ fn contains_many_in_illegal_pos(&self) -> bool {

+ match self {

+ Expr::Method { target, .. } => target.contains_many_in_illegal_pos(),

+ Expr::Field { expr, .. } => expr.contains_many_in_illegal_pos(),

+ Expr::Reference(target) => target.is_many(),

+ Expr::Many(_) => true,

+ _ => false,

+ }

+ }

+

+ /// Helper function to check if outermost type tree is `Expr::Many` variant

+ pub fn is_many(&self) -> bool {

+ matches!(self, Expr::Many(_))

+ }

+}

+//! Tactics for term search

+//!

+//! All the tactics take following arguments

+//! * `ctx` - Context for the term search

+//! * `defs` - Set of items in scope at term search target location

+//! * `lookup` - Lookup table for types

+//! And they return iterator that yields type trees that unify with the `goal` type.

+

+use std::iter;

+

+use hir_ty::db::HirDatabase;

+use hir_ty::mir::BorrowKind;

+use hir_ty::TyBuilder;

+use itertools::Itertools;

+use rustc_hash::FxHashSet;

+

+use crate::{

+ Adt, AssocItem, Enum, GenericDef, GenericParam, HasVisibility, Impl, ModuleDef, ScopeDef, Type,

+ TypeParam, Variant,

+};

+

+use crate::term_search::{Expr, TermSearchConfig};

+

+use super::{LookupTable, NewTypesKey, TermSearchCtx};

+

+/// # Trivial tactic

+///

+/// Attempts to fulfill the goal by trying items in scope

+/// Also works as a starting point to move all items in scope to lookup table.

+///

+/// # Arguments

+/// * `ctx` - Context for the term search

+/// * `defs` - Set of items in scope at term search target location

+/// * `lookup` - Lookup table for types

+///

+/// Returns iterator that yields elements that unify with `goal`.

+///

+/// _Note that there is no use of calling this tactic in every iteration as the output does not

+/// depend on the current state of `lookup`_

+pub(super) fn trivial<'a, DB: HirDatabase>(

+ ctx: &'a TermSearchCtx<'a, DB>,

+ defs: &'a FxHashSet<ScopeDef>,

+ lookup: &'a mut LookupTable,

+) -> impl Iterator<Item = Expr> + 'a {

+ let db = ctx.sema.db;

+ defs.iter().filter_map(|def| {

+ let expr = match def {

+ ScopeDef::ModuleDef(ModuleDef::Const(it)) => Some(Expr::Const(*it)),

+ ScopeDef::ModuleDef(ModuleDef::Static(it)) => Some(Expr::Static(*it)),

+ ScopeDef::GenericParam(GenericParam::ConstParam(it)) => Some(Expr::ConstParam(*it)),

+ ScopeDef::Local(it) => {

+ if ctx.config.enable_borrowcheck {

+ let borrowck = db.borrowck(it.parent).ok()?;

+

+ let invalid = borrowck.iter().any(|b| {

+ b.partially_moved.iter().any(|moved| {

+ Some(&moved.local) == b.mir_body.binding_locals.get(it.binding_id)

+ }) || b.borrow_regions.iter().any(|region| {

+ // Shared borrows are fine

+ Some(&region.local) == b.mir_body.binding_locals.get(it.binding_id)

+ && region.kind != BorrowKind::Shared

+ })

+ });

+

+ if invalid {

+ return None;

+ }

+ }

+

+ Some(Expr::Local(*it))

+ }

+ _ => None,

+ }?;

+

+ lookup.mark_exhausted(*def);

+

+ let ty = expr.ty(db);

+ lookup.insert(ty.clone(), std::iter::once(expr.clone()));

+

+ // Don't suggest local references as they are not valid for return

+ if matches!(expr, Expr::Local(_)) && ty.contains_reference(db) {

+ return None;

+ }

+

+ ty.could_unify_with_deeply(db, &ctx.goal).then_some(expr)

+ })

+}

+

+/// # Type constructor tactic

+///

+/// Attempts different type constructors for enums and structs in scope

+///

+/// Updates lookup by new types reached and returns iterator that yields

+/// elements that unify with `goal`.

+///

+/// # Arguments

+/// * `ctx` - Context for the term search

+/// * `defs` - Set of items in scope at term search target location

+/// * `lookup` - Lookup table for types

+pub(super) fn type_constructor<'a, DB: HirDatabase>(

+ ctx: &'a TermSearchCtx<'a, DB>,

+ defs: &'a FxHashSet<ScopeDef>,

+ lookup: &'a mut LookupTable,

+) -> impl Iterator<Item = Expr> + 'a {

+ let db = ctx.sema.db;

+ let module = ctx.scope.module();

+ fn variant_helper(

+ db: &dyn HirDatabase,

+ lookup: &mut LookupTable,

+ parent_enum: Enum,

+ variant: Variant,

+ goal: &Type,

+ config: &TermSearchConfig,

+ ) -> Vec<(Type, Vec<Expr>)> {

+ // Ignore unstable

+ if variant.is_unstable(db) {

+ return Vec::new();

+ }

+

+ let generics = GenericDef::from(variant.parent_enum(db));

+ let Some(type_params) = generics

+ .type_or_const_params(db)

+ .into_iter()

+ .map(|it| it.as_type_param(db))

+ .collect::<Option<Vec<TypeParam>>>()

+ else {

+ // Ignore enums with const generics

+ return Vec::new();

+ };

+

+ // We currently do not check lifetime bounds so ignore all types that have something to do

+ // with them

+ if !generics.lifetime_params(db).is_empty() {

+ return Vec::new();

+ }

+

+ // Only account for stable type parameters for now, unstable params can be default

+ // tho, for example in `Box<T, #[unstable] A: Allocator>`

+ if type_params.iter().any(|it| it.is_unstable(db) && it.default(db).is_none()) {

+ return Vec::new();

+ }

+

+ let non_default_type_params_len =

+ type_params.iter().filter(|it| it.default(db).is_none()).count();

+

+ let generic_params = lookup

+ .iter_types()

+ .collect::<Vec<_>>() // Force take ownership

+ .into_iter()

+ .permutations(non_default_type_params_len);

+

+ generic_params

+ .filter_map(move |generics| {

+ // Insert default type params

+ let mut g = generics.into_iter();

+ let generics: Vec<_> = type_params

+ .iter()

+ .map(|it| it.default(db).unwrap_or_else(|| g.next().expect("No generic")))

+ .collect();

+

+ let enum_ty = Adt::from(parent_enum).ty_with_args(db, generics.iter().cloned());

+

+ // Allow types with generics only if they take us straight to goal for

+ // performance reasons

+ if !generics.is_empty() && !enum_ty.could_unify_with_deeply(db, goal) {

+ return None;

+ }

+

+ // Ignore types that have something to do with lifetimes

+ if config.enable_borrowcheck && enum_ty.contains_reference(db) {

+ return None;

+ }

+

+ // Early exit if some param cannot be filled from lookup

+ let param_exprs: Vec<Vec<Expr>> = variant

+ .fields(db)

+ .into_iter()

+ .map(|field| lookup.find(db, &field.ty_with_args(db, generics.iter().cloned())))

+ .collect::<Option<_>>()?;

+

+ // Note that we need special case for 0 param constructors because of multi cartesian

+ // product

+ let variant_exprs: Vec<Expr> = if param_exprs.is_empty() {

+ vec![Expr::Variant { variant, generics: generics.clone(), params: Vec::new() }]

+ } else {

+ param_exprs

+ .into_iter()

+ .multi_cartesian_product()

+ .map(|params| Expr::Variant { variant, generics: generics.clone(), params })

+ .collect()

+ };

+ lookup.insert(enum_ty.clone(), variant_exprs.iter().cloned());

+

+ Some((enum_ty, variant_exprs))

+ })

+ .collect()

+ }

+ defs.iter()

+ .filter_map(move |def| match def {

+ ScopeDef::ModuleDef(ModuleDef::Variant(it)) => {

+ let variant_exprs =

+ variant_helper(db, lookup, it.parent_enum(db), *it, &ctx.goal, &ctx.config);

+ if variant_exprs.is_empty() {

+ return None;

+ }

+ lookup.mark_fulfilled(ScopeDef::ModuleDef(ModuleDef::Variant(*it)));

+ Some(variant_exprs)

+ }

+ ScopeDef::ModuleDef(ModuleDef::Adt(Adt::Enum(enum_))) => {

+ let exprs: Vec<(Type, Vec<Expr>)> = enum_

+ .variants(db)

+ .into_iter()

+ .flat_map(|it| variant_helper(db, lookup, *enum_, it, &ctx.goal, &ctx.config))

+ .collect();

+

+ if !exprs.is_empty() {

+ lookup.mark_fulfilled(ScopeDef::ModuleDef(ModuleDef::Adt(Adt::Enum(*enum_))));

+ }

+

+ Some(exprs)

+ }

+ ScopeDef::ModuleDef(ModuleDef::Adt(Adt::Struct(it))) => {

+ // Ignore unstable and not visible

+ if it.is_unstable(db) || !it.is_visible_from(db, module) {

+ return None;

+ }

+

+ let generics = GenericDef::from(*it);

+

+ // Ignore const params for now

+ let type_params = generics

+ .type_or_const_params(db)

+ .into_iter()

+ .map(|it| it.as_type_param(db))

+ .collect::<Option<Vec<TypeParam>>>()?;

+

+ // We currently do not check lifetime bounds so ignore all types that have something to do

+ // with them

+ if !generics.lifetime_params(db).is_empty() {

+ return None;

+ }

+

+ // Only account for stable type parameters for now, unstable params can be default

+ // tho, for example in `Box<T, #[unstable] A: Allocator>`

+ if type_params.iter().any(|it| it.is_unstable(db) && it.default(db).is_none()) {

+ return None;

+ }

+

+ let non_default_type_params_len =

+ type_params.iter().filter(|it| it.default(db).is_none()).count();

+

+ let generic_params = lookup

+ .iter_types()

+ .collect::<Vec<_>>() // Force take ownership

+ .into_iter()

+ .permutations(non_default_type_params_len);

+

+ let exprs = generic_params

+ .filter_map(|generics| {

+ // Insert default type params

+ let mut g = generics.into_iter();

+ let generics: Vec<_> = type_params

+ .iter()

+ .map(|it| {

+ it.default(db)

+ .unwrap_or_else(|| g.next().expect("Missing type param"))

+ })

+ .collect();

+

+ let struct_ty = Adt::from(*it).ty_with_args(db, generics.iter().cloned());

+

+ // Allow types with generics only if they take us straight to goal for

+ // performance reasons

+ if non_default_type_params_len != 0

+ && struct_ty.could_unify_with_deeply(db, &ctx.goal)

+ {

+ return None;

+ }

+

+ // Ignore types that have something to do with lifetimes

+ if ctx.config.enable_borrowcheck && struct_ty.contains_reference(db) {

+ return None;

+ }

+ let fileds = it.fields(db);

+ // Check if all fields are visible, otherwise we cannot fill them

+ if fileds.iter().any(|it| !it.is_visible_from(db, module)) {

+ return None;

+ }

+

+ // Early exit if some param cannot be filled from lookup

+ let param_exprs: Vec<Vec<Expr>> = fileds

+ .into_iter()

+ .map(|field| lookup.find(db, &field.ty(db)))

+ .collect::<Option<_>>()?;

+

+ // Note that we need special case for 0 param constructors because of multi cartesian

+ // product

+ let struct_exprs: Vec<Expr> = if param_exprs.is_empty() {

+ vec![Expr::Struct { strukt: *it, generics, params: Vec::new() }]

+ } else {

+ param_exprs

+ .into_iter()

+ .multi_cartesian_product()

+ .map(|params| Expr::Struct {

+ strukt: *it,

+ generics: generics.clone(),

+ params,

+ })

+ .collect()

+ };

+

+ lookup

+ .mark_fulfilled(ScopeDef::ModuleDef(ModuleDef::Adt(Adt::Struct(*it))));

+ lookup.insert(struct_ty.clone(), struct_exprs.iter().cloned());

+

+ Some((struct_ty, struct_exprs))

+ })

+ .collect();

+ Some(exprs)

+ }

+ _ => None,

+ })

+ .flatten()

+ .filter_map(|(ty, exprs)| ty.could_unify_with_deeply(db, &ctx.goal).then_some(exprs))

+ .flatten()

+}

+

+/// # Free function tactic

+///

+/// Attempts to call different functions in scope with parameters from lookup table.

+/// Functions that include generics are not used for performance reasons.

+///

+/// Updates lookup by new types reached and returns iterator that yields

+/// elements that unify with `goal`.

+///

+/// # Arguments

+/// * `ctx` - Context for the term search

+/// * `defs` - Set of items in scope at term search target location

+/// * `lookup` - Lookup table for types

+pub(super) fn free_function<'a, DB: HirDatabase>(

+ ctx: &'a TermSearchCtx<'a, DB>,

+ defs: &'a FxHashSet<ScopeDef>,

+ lookup: &'a mut LookupTable,

+) -> impl Iterator<Item = Expr> + 'a {

+ let db = ctx.sema.db;

+ let module = ctx.scope.module();

+ defs.iter()

+ .filter_map(move |def| match def {

+ ScopeDef::ModuleDef(ModuleDef::Function(it)) => {

+ let generics = GenericDef::from(*it);

+

+ // Ignore const params for now

+ let type_params = generics

+ .type_or_const_params(db)

+ .into_iter()

+ .map(|it| it.as_type_param(db))

+ .collect::<Option<Vec<TypeParam>>>()?;

+

+ // Ignore lifetimes as we do not check them

+ if !generics.lifetime_params(db).is_empty() {

+ return None;

+ }

+

+ // Only account for stable type parameters for now, unstable params can be default

+ // tho, for example in `Box<T, #[unstable] A: Allocator>`

+ if type_params.iter().any(|it| it.is_unstable(db) && it.default(db).is_none()) {

+ return None;

+ }

+

+ let non_default_type_params_len =

+ type_params.iter().filter(|it| it.default(db).is_none()).count();

+

+ // Ignore bigger number of generics for now as they kill the performance

+ if non_default_type_params_len > 0 {

+ return None;

+ }

+

+ let generic_params = lookup

+ .iter_types()

+ .collect::<Vec<_>>() // Force take ownership

+ .into_iter()

+ .permutations(non_default_type_params_len);

+

+ let exprs: Vec<_> = generic_params

+ .filter_map(|generics| {

+ // Insert default type params

+ let mut g = generics.into_iter();

+ let generics: Vec<_> = type_params

+ .iter()

+ .map(|it| match it.default(db) {

+ Some(ty) => Some(ty),

+ None => {

+ let generic = g.next().expect("Missing type param");

+ // Filter out generics that do not unify due to trait bounds

+ it.ty(db).could_unify_with(db, &generic).then_some(generic)

+ }

+ })

+ .collect::<Option<_>>()?;

+

+ let ret_ty = it.ret_type_with_args(db, generics.iter().cloned());

+ // Filter out private and unsafe functions

+ if !it.is_visible_from(db, module)

+ || it.is_unsafe_to_call(db)

+ || it.is_unstable(db)

+ || ctx.config.enable_borrowcheck && ret_ty.contains_reference(db)

+ || ret_ty.is_raw_ptr()

+ {

+ return None;

+ }

+

+ // Early exit if some param cannot be filled from lookup

+ let param_exprs: Vec<Vec<Expr>> = it

+ .params_without_self_with_args(db, generics.iter().cloned())

+ .into_iter()

+ .map(|field| {

+ let ty = field.ty();

+ match ty.is_mutable_reference() {

+ true => None,

+ false => lookup.find_autoref(db, ty),

+ }

+ })

+ .collect::<Option<_>>()?;

+

+ // Note that we need special case for 0 param constructors because of multi cartesian

+ // product

+ let fn_exprs: Vec<Expr> = if param_exprs.is_empty() {

+ vec![Expr::Function { func: *it, generics, params: Vec::new() }]

+ } else {

+ param_exprs

+ .into_iter()

+ .multi_cartesian_product()

+ .map(|params| Expr::Function {

+ func: *it,

+ generics: generics.clone(),

+

+ params,

+ })

+ .collect()

+ };

+

+ lookup.mark_fulfilled(ScopeDef::ModuleDef(ModuleDef::Function(*it)));

+ lookup.insert(ret_ty.clone(), fn_exprs.iter().cloned());

+ Some((ret_ty, fn_exprs))

+ })

+ .collect();

+ Some(exprs)

+ }

+ _ => None,

+ })

+ .flatten()

+ .filter_map(|(ty, exprs)| ty.could_unify_with_deeply(db, &ctx.goal).then_some(exprs))

+ .flatten()

+}

+

+/// # Impl method tactic

+///

+/// Attempts to to call methods on types from lookup table.

+/// This includes both functions from direct impl blocks as well as functions from traits.

+/// Methods defined in impl blocks that are generic and methods that are themselves have

+/// generics are ignored for performance reasons.

+///

+/// Updates lookup by new types reached and returns iterator that yields

+/// elements that unify with `goal`.

+///

+/// # Arguments

+/// * `ctx` - Context for the term search

+/// * `defs` - Set of items in scope at term search target location

+/// * `lookup` - Lookup table for types

+pub(super) fn impl_method<'a, DB: HirDatabase>(

+ ctx: &'a TermSearchCtx<'a, DB>,

+ _defs: &'a FxHashSet<ScopeDef>,

+ lookup: &'a mut LookupTable,

+) -> impl Iterator<Item = Expr> + 'a {

+ let db = ctx.sema.db;

+ let module = ctx.scope.module();

+ lookup

+ .new_types(NewTypesKey::ImplMethod)

+ .into_iter()

+ .flat_map(|ty| {

+ Impl::all_for_type(db, ty.clone()).into_iter().map(move |imp| (ty.clone(), imp))

+ })

+ .flat_map(|(ty, imp)| imp.items(db).into_iter().map(move |item| (imp, ty.clone(), item)))

+ .filter_map(|(imp, ty, it)| match it {

+ AssocItem::Function(f) => Some((imp, ty, f)),

+ _ => None,

+ })

+ .filter_map(move |(imp, ty, it)| {

+ let fn_generics = GenericDef::from(it);

+ let imp_generics = GenericDef::from(imp);

+

+ // Ignore const params for now

+ let imp_type_params = imp_generics

+ .type_or_const_params(db)

+ .into_iter()

+ .map(|it| it.as_type_param(db))

+ .collect::<Option<Vec<TypeParam>>>()?;

+

+ // Ignore const params for now

+ let fn_type_params = fn_generics

+ .type_or_const_params(db)

+ .into_iter()

+ .map(|it| it.as_type_param(db))

+ .collect::<Option<Vec<TypeParam>>>()?;

+

+ // Ignore all functions that have something to do with lifetimes as we don't check them

+ if !fn_generics.lifetime_params(db).is_empty() {

+ return None;

+ }

+

+ // Ignore functions without self param

+ if !it.has_self_param(db) {

+ return None;

+ }

+

+ // Filter out private and unsafe functions

+ if !it.is_visible_from(db, module) || it.is_unsafe_to_call(db) || it.is_unstable(db) {

+ return None;

+ }

+

+ // Only account for stable type parameters for now, unstable params can be default

+ // tho, for example in `Box<T, #[unstable] A: Allocator>`

+ if imp_type_params.iter().any(|it| it.is_unstable(db) && it.default(db).is_none())

+ || fn_type_params.iter().any(|it| it.is_unstable(db) && it.default(db).is_none())

+ {

+ return None;

+ }

+

+ let non_default_type_params_len = imp_type_params

+ .iter()

+ .chain(fn_type_params.iter())

+ .filter(|it| it.default(db).is_none())

+ .count();

+

+ // Ignore bigger number of generics for now as they kill the performance

+ if non_default_type_params_len > 0 {

+ return None;

+ }

+

+ let generic_params = lookup

+ .iter_types()

+ .collect::<Vec<_>>() // Force take ownership

+ .into_iter()

+ .permutations(non_default_type_params_len);

+

+ let exprs: Vec<_> = generic_params

+ .filter_map(|generics| {

+ // Insert default type params

+ let mut g = generics.into_iter();

+ let generics: Vec<_> = imp_type_params

+ .iter()

+ .chain(fn_type_params.iter())

+ .map(|it| match it.default(db) {

+ Some(ty) => Some(ty),

+ None => {

+ let generic = g.next().expect("Missing type param");

+ // Filter out generics that do not unify due to trait bounds

+ it.ty(db).could_unify_with(db, &generic).then_some(generic)

+ }

+ })

+ .collect::<Option<_>>()?;

+

+ let ret_ty = it.ret_type_with_args(

+ db,

+ ty.type_arguments().chain(generics.iter().cloned()),

+ );

+ // Filter out functions that return references

+ if ctx.config.enable_borrowcheck && ret_ty.contains_reference(db)

+ || ret_ty.is_raw_ptr()

+ {

+ return None;

+ }

+

+ // Ignore functions that do not change the type

+ if ty.could_unify_with_deeply(db, &ret_ty) {

+ return None;

+ }

+

+ let self_ty = it

+ .self_param(db)

+ .expect("No self param")

+ .ty_with_args(db, ty.type_arguments().chain(generics.iter().cloned()));

+

+ // Ignore functions that have different self type

+ if !self_ty.autoderef(db).any(|s_ty| ty == s_ty) {

+ return None;

+ }

+

+ let target_type_exprs = lookup.find(db, &ty).expect("Type not in lookup");

+

+ // Early exit if some param cannot be filled from lookup

+ let param_exprs: Vec<Vec<Expr>> = it

+ .params_without_self_with_args(

+ db,

+ ty.type_arguments().chain(generics.iter().cloned()),

+ )

+ .into_iter()

+ .map(|field| lookup.find_autoref(db, field.ty()))

+ .collect::<Option<_>>()?;

+

+ let fn_exprs: Vec<Expr> = std::iter::once(target_type_exprs)

+ .chain(param_exprs)

+ .multi_cartesian_product()

+ .map(|params| {

+ let mut params = params.into_iter();

+ let target = Box::new(params.next().unwrap());

+ Expr::Method {

+ func: it,

+ generics: generics.clone(),

+ target,

+ params: params.collect(),

+ }

+ })

+ .collect();

+

+ lookup.insert(ret_ty.clone(), fn_exprs.iter().cloned());

+ Some((ret_ty, fn_exprs))

+ })

+ .collect();

+ Some(exprs)

+ })

+ .flatten()

+ .filter_map(|(ty, exprs)| ty.could_unify_with_deeply(db, &ctx.goal).then_some(exprs))

+ .flatten()

+}

+

+/// # Struct projection tactic

+///

+/// Attempts different struct fields (`foo.bar.baz`)

+///

+/// Updates lookup by new types reached and returns iterator that yields

+/// elements that unify with `goal`.

+///

+/// # Arguments

+/// * `ctx` - Context for the term search

+/// * `defs` - Set of items in scope at term search target location

+/// * `lookup` - Lookup table for types

+pub(super) fn struct_projection<'a, DB: HirDatabase>(

+ ctx: &'a TermSearchCtx<'a, DB>,

+ _defs: &'a FxHashSet<ScopeDef>,

+ lookup: &'a mut LookupTable,

+) -> impl Iterator<Item = Expr> + 'a {

+ let db = ctx.sema.db;

+ let module = ctx.scope.module();

+ lookup

+ .new_types(NewTypesKey::StructProjection)

+ .into_iter()

+ .map(|ty| (ty.clone(), lookup.find(db, &ty).expect("Expr not in lookup")))

+ .flat_map(move |(ty, targets)| {

+ ty.fields(db).into_iter().filter_map(move |(field, filed_ty)| {

+ if !field.is_visible_from(db, module) {

+ return None;

+ }

+ let exprs = targets

+ .clone()

+ .into_iter()

+ .map(move |target| Expr::Field { field, expr: Box::new(target) });

+ Some((filed_ty, exprs))

+ })

+ })

+ .filter_map(|(ty, exprs)| ty.could_unify_with_deeply(db, &ctx.goal).then_some(exprs))

+ .flatten()

+}

+

+/// # Famous types tactic

+///

+/// Attempts different values of well known types such as `true` or `false`.

+///

+/// Updates lookup by new types reached and returns iterator that yields

+/// elements that unify with `goal`.

+///

+/// _Note that there is no point of calling it iteratively as the output is always the same_

+///

+/// # Arguments

+/// * `ctx` - Context for the term search

+/// * `defs` - Set of items in scope at term search target location

+/// * `lookup` - Lookup table for types

+pub(super) fn famous_types<'a, DB: HirDatabase>(

+ ctx: &'a TermSearchCtx<'a, DB>,

+ _defs: &'a FxHashSet<ScopeDef>,

+ lookup: &'a mut LookupTable,

+) -> impl Iterator<Item = Expr> + 'a {

+ let db = ctx.sema.db;

+ let module = ctx.scope.module();

+ [

+ Expr::FamousType { ty: Type::new(db, module.id, TyBuilder::bool()), value: "true" },

+ Expr::FamousType { ty: Type::new(db, module.id, TyBuilder::bool()), value: "false" },

+ Expr::FamousType { ty: Type::new(db, module.id, TyBuilder::unit()), value: "()" },

+ ]

+ .into_iter()

+ .map(|exprs| {

+ lookup.insert(exprs.ty(db), std::iter::once(exprs.clone()));

+ exprs

+ })

+ .filter(|expr| expr.ty(db).could_unify_with_deeply(db, &ctx.goal))

+}

+

+/// # Impl static method (without self type) tactic

+///

+/// Attempts different functions from impl blocks that take no self parameter.

+///

+/// Updates lookup by new types reached and returns iterator that yields

+/// elements that unify with `goal`.

+///

+/// # Arguments

+/// * `ctx` - Context for the term search

+/// * `defs` - Set of items in scope at term search target location

+/// * `lookup` - Lookup table for types

+pub(super) fn impl_static_method<'a, DB: HirDatabase>(

+ ctx: &'a TermSearchCtx<'a, DB>,

+ _defs: &'a FxHashSet<ScopeDef>,

+ lookup: &'a mut LookupTable,

+) -> impl Iterator<Item = Expr> + 'a {

+ let db = ctx.sema.db;

+ let module = ctx.scope.module();

+ lookup

+ .take_types_wishlist()

+ .into_iter()

+ .chain(iter::once(ctx.goal.clone()))

+ .flat_map(|ty| {

+ Impl::all_for_type(db, ty.clone()).into_iter().map(move |imp| (ty.clone(), imp))

+ })

+ .filter(|(_, imp)| !imp.is_unsafe(db))

+ .flat_map(|(ty, imp)| imp.items(db).into_iter().map(move |item| (imp, ty.clone(), item)))

+ .filter_map(|(imp, ty, it)| match it {

+ AssocItem::Function(f) => Some((imp, ty, f)),

+ _ => None,

+ })

+ .filter_map(move |(imp, ty, it)| {

+ let fn_generics = GenericDef::from(it);

+ let imp_generics = GenericDef::from(imp);

+

+ // Ignore const params for now

+ let imp_type_params = imp_generics

+ .type_or_const_params(db)

+ .into_iter()

+ .map(|it| it.as_type_param(db))

+ .collect::<Option<Vec<TypeParam>>>()?;

+

+ // Ignore const params for now

+ let fn_type_params = fn_generics

+ .type_or_const_params(db)

+ .into_iter()

+ .map(|it| it.as_type_param(db))

+ .collect::<Option<Vec<TypeParam>>>()?;

+

+ // Ignore all functions that have something to do with lifetimes as we don't check them

+ if !fn_generics.lifetime_params(db).is_empty()

+ || !imp_generics.lifetime_params(db).is_empty()

+ {

+ return None;

+ }

+

+ // Ignore functions with self param

+ if it.has_self_param(db) {

+ return None;

+ }

+

+ // Filter out private and unsafe functions

+ if !it.is_visible_from(db, module) || it.is_unsafe_to_call(db) || it.is_unstable(db) {

+ return None;

+ }

+

+ // Only account for stable type parameters for now, unstable params can be default

+ // tho, for example in `Box<T, #[unstable] A: Allocator>`

+ if imp_type_params.iter().any(|it| it.is_unstable(db) && it.default(db).is_none())

+ || fn_type_params.iter().any(|it| it.is_unstable(db) && it.default(db).is_none())

+ {

+ return None;

+ }

+

+ let non_default_type_params_len = imp_type_params

+ .iter()

+ .chain(fn_type_params.iter())

+ .filter(|it| it.default(db).is_none())

+ .count();

+

+ // Ignore bigger number of generics for now as they kill the performance

+ if non_default_type_params_len > 1 {

+ return None;

+ }

+

+ let generic_params = lookup

+ .iter_types()

+ .collect::<Vec<_>>() // Force take ownership

+ .into_iter()

+ .permutations(non_default_type_params_len);

+

+ let exprs: Vec<_> = generic_params

+ .filter_map(|generics| {

+ // Insert default type params

+ let mut g = generics.into_iter();

+ let generics: Vec<_> = imp_type_params

+ .iter()

+ .chain(fn_type_params.iter())

+ .map(|it| match it.default(db) {

+ Some(ty) => Some(ty),

+ None => {

+ let generic = g.next().expect("Missing type param");

+ it.trait_bounds(db)

+ .into_iter()

+ .all(|bound| generic.impls_trait(db, bound, &[]));

+ // Filter out generics that do not unify due to trait bounds

+ it.ty(db).could_unify_with(db, &generic).then_some(generic)

+ }

+ })

+ .collect::<Option<_>>()?;

+

+ let ret_ty = it.ret_type_with_args(

+ db,

+ ty.type_arguments().chain(generics.iter().cloned()),

+ );

+ // Filter out functions that return references

+ if ctx.config.enable_borrowcheck && ret_ty.contains_reference(db)

+ || ret_ty.is_raw_ptr()

+ {

+ return None;

+ }

+

+ // Ignore functions that do not change the type

+ // if ty.could_unify_with_deeply(db, &ret_ty) {

+ // return None;

+ // }

+

+ // Early exit if some param cannot be filled from lookup

+ let param_exprs: Vec<Vec<Expr>> = it

+ .params_without_self_with_args(

+ db,

+ ty.type_arguments().chain(generics.iter().cloned()),

+ )

+ .into_iter()

+ .map(|field| lookup.find_autoref(db, field.ty()))

+ .collect::<Option<_>>()?;

+

+ // Note that we need special case for 0 param constructors because of multi cartesian

+ // product

+ let fn_exprs: Vec<Expr> = if param_exprs.is_empty() {

+ vec![Expr::Function { func: it, generics, params: Vec::new() }]

+ } else {

+ param_exprs

+ .into_iter()

+ .multi_cartesian_product()

+ .map(|params| Expr::Function {

+ func: it,

+ generics: generics.clone(),

+ params,

+ })

+ .collect()

+ };

+

+ lookup.insert(ret_ty.clone(), fn_exprs.iter().cloned());

+ Some((ret_ty, fn_exprs))

+ })

+ .collect();

+ Some(exprs)

+ })

+ .flatten()

+ .filter_map(|(ty, exprs)| ty.could_unify_with_deeply(db, &ctx.goal).then_some(exprs))

+ .flatten()

+}

+ vis_owner.set_visibility(Some(missing_visibility.clone_for_update()));

+ vis_owner.set_visibility(Some(missing_visibility.clone_for_update()));

+ ast::{

+ self,

+ edit_in_place::{HasVisibilityEdit, Indent},

+ make, HasGenericParams, HasName,

+ },

+ ted::{self, Position},

+ AstNode, SyntaxKind, T,

+// trait ${0:NewTrait}<const N: usize> {

+// impl<const N: usize> ${0:NewTrait}<N> for Foo<N> {

+ let impl_ast = builder.make_mut(impl_ast);

+ let impl_items = builder.make_mut(assoc_items);

+ let impl_name = builder.make_mut(impl_name);

+ )

+ .clone_for_update();

+

+ let trait_name = trait_ast.name().expect("new trait should have a name");

+ let trait_name_ref = make::name_ref(&trait_name.to_string()).clone_for_update();

+ let mut elements = vec![

+ trait_name_ref.syntax().clone().into(),

+ make::tokens::single_space().into(),

+ make::token(T![for]).into(),

+ ];

+

+ if let Some(params) = impl_ast.generic_param_list() {

+ let gen_args = &params.to_generic_args().clone_for_update();

+ elements.insert(1, gen_args.syntax().clone().into());

+ }

+ ted::insert_all(Position::before(impl_name.syntax()), elements);

+

+ // Insert trait before TraitImpl

+ ted::insert_all_raw(

+ Position::before(impl_ast.syntax()),

+ vec![

+ trait_ast.syntax().clone().into(),

+ make::tokens::whitespace(&format!("\n\n{}", impl_ast.indent_level())).into(),

+ ],

+ );

+ // Link the trait name & trait ref names together as a placeholder snippet group

+ if let Some(cap) = ctx.config.snippet_cap {

+ builder.add_placeholder_snippet_group(

+ cap,

+ vec![trait_name.syntax().clone(), trait_name_ref.syntax().clone()],

+ if let Some(has_vis) = ast::AnyHasVisibility::cast(item.syntax().clone()) {

+ has_vis.set_visibility(None);

+trait ${0:NewTrait}<const N: usize> {

+impl<const N: usize> ${0:NewTrait}<N> for Foo<N> {

+//! Term search assist

+use hir::term_search::TermSearchCtx;

+use ide_db::{

+ assists::{AssistId, AssistKind, GroupLabel},

+ famous_defs::FamousDefs,

+};

+

+use itertools::Itertools;

+use syntax::{ast, AstNode};

+

+use crate::assist_context::{AssistContext, Assists};

+

+pub(crate) fn term_search(acc: &mut Assists, ctx: &AssistContext<'_>) -> Option<()> {

+ let unexpanded = ctx.find_node_at_offset::<ast::MacroCall>()?;

+ let syntax = unexpanded.syntax();

+ let goal_range = syntax.text_range();

+

+ let parent = syntax.parent()?;

+ let scope = ctx.sema.scope(&parent)?;

+

+ let macro_call = ctx.sema.resolve_macro_call(&unexpanded)?;

+

+ let famous_defs = FamousDefs(&ctx.sema, scope.krate());

+ let std_todo = famous_defs.core_macros_todo()?;

+ let std_unimplemented = famous_defs.core_macros_unimplemented()?;

+

+ if macro_call != std_todo && macro_call != std_unimplemented {

+ return None;

+ }

+

+ let target_ty = ctx.sema.type_of_expr(&ast::Expr::cast(parent.clone())?)?.adjusted();

+

+ let term_search_ctx = TermSearchCtx {

+ sema: &ctx.sema,

+ scope: &scope,

+ goal: target_ty,

+ config: Default::default(),

+ };

+ let paths = hir::term_search::term_search(&term_search_ctx);

+

+ if paths.is_empty() {

+ return None;

+ }

+

+ let mut formatter = |_: &hir::Type| String::from("todo!()");

+

+ let paths = paths

+ .into_iter()

+ .filter_map(|path| {

+ path.gen_source_code(

+ &scope,

+ &mut formatter,

+ ctx.config.prefer_no_std,

+ ctx.config.prefer_prelude,

+ )

+ .ok()

+ })

+ .unique();

+

+ for code in paths {

+ acc.add_group(

+ &GroupLabel(String::from("Term search")),

+ AssistId("term_search", AssistKind::Generate),

+ format!("Replace todo!() with {code}"),

+ goal_range,

+ |builder| {

+ builder.replace(goal_range, code);

+ },

+ );

+ }

+

+ Some(())

+}

+

+#[cfg(test)]

+mod tests {

+ use crate::tests::{check_assist, check_assist_not_applicable};

+

+ use super::*;

+

+ #[test]

+ fn test_complete_local() {

+ check_assist(

+ term_search,

+ r#"//- minicore: todo, unimplemented

+fn f() { let a: u128 = 1; let b: u128 = todo$0!() }"#,

+ r#"fn f() { let a: u128 = 1; let b: u128 = a }"#,

+ )

+ }

+

+ #[test]

+ fn test_complete_todo_with_msg() {

+ check_assist(

+ term_search,

+ r#"//- minicore: todo, unimplemented

+fn f() { let a: u128 = 1; let b: u128 = todo$0!("asd") }"#,

+ r#"fn f() { let a: u128 = 1; let b: u128 = a }"#,

+ )

+ }

+

+ #[test]

+ fn test_complete_unimplemented_with_msg() {

+ check_assist(

+ term_search,

+ r#"//- minicore: todo, unimplemented

+fn f() { let a: u128 = 1; let b: u128 = todo$0!("asd") }"#,

+ r#"fn f() { let a: u128 = 1; let b: u128 = a }"#,

+ )

+ }

+

+ #[test]

+ fn test_complete_unimplemented() {

+ check_assist(

+ term_search,

+ r#"//- minicore: todo, unimplemented

+fn f() { let a: u128 = 1; let b: u128 = todo$0!("asd") }"#,

+ r#"fn f() { let a: u128 = 1; let b: u128 = a }"#,

+ )

+ }

+

+ #[test]

+ fn test_complete_struct_field() {

+ check_assist(

+ term_search,

+ r#"//- minicore: todo, unimplemented

+struct A { pub x: i32, y: bool }

+fn f() { let a = A { x: 1, y: true }; let b: i32 = todo$0!(); }"#,

+ r#"struct A { pub x: i32, y: bool }

+fn f() { let a = A { x: 1, y: true }; let b: i32 = a.x; }"#,

+ )

+ }

+

+ #[test]

+ fn test_enum_with_generics() {

+ check_assist(

+ term_search,

+ r#"//- minicore: todo, unimplemented, option

+fn f() { let a: i32 = 1; let b: Option<i32> = todo$0!(); }"#,

+ r#"fn f() { let a: i32 = 1; let b: Option<i32> = None; }"#,

+ )

+ }

+

+ #[test]

+ fn test_enum_with_generics2() {