crates/hir_def/src/body/scope.rs

   1 //! Name resolution for expressions.
   2 use std::sync::Arc;
   3
   4 use hir_expand::name::Name;
   5 use la_arena::{Arena, Idx};
   6 use rustc_hash::FxHashMap;
   7
   8 use crate::{
   9     body::Body,
  10     db::DefDatabase,
  11     expr::{Expr, ExprId, LabelId, MatchGuard, Pat, PatId, Statement},
  12     BlockId, DefWithBodyId,
  13 };
  14
  15 pub type ScopeId = Idx<ScopeData>;
  16
  17 #[derive(Debug, PartialEq, Eq)]
  18 pub struct ExprScopes {
  19     scopes: Arena<ScopeData>,
  20     scope_by_expr: FxHashMap<ExprId, ScopeId>,
  21 }
  22
  23 #[derive(Debug, PartialEq, Eq)]
  24 pub struct ScopeEntry {
  25     name: Name,
  26     pat: PatId,
  27 }
  28
  29 impl ScopeEntry {
  30     pub fn name(&self) -> &Name {
  31         &self.name
  32     }
  33
  34     pub fn pat(&self) -> PatId {
  35         self.pat
  36     }
  37 }
  38
  39 #[derive(Debug, PartialEq, Eq)]
  40 pub struct ScopeData {
  41     parent: Option<ScopeId>,
  42     block: Option<BlockId>,
  43     label: Option<(LabelId, Name)>,
  44     entries: Vec<ScopeEntry>,
  45 }
  46
  47 impl ExprScopes {
  48     pub(crate) fn expr_scopes_query(db: &dyn DefDatabase, def: DefWithBodyId) -> Arc<ExprScopes> {
  49         let body = db.body(def);
  50         Arc::new(ExprScopes::new(&*body))
  51     }
  52
  53     fn new(body: &Body) -> ExprScopes {
  54         let mut scopes =
  55             ExprScopes { scopes: Arena::default(), scope_by_expr: FxHashMap::default() };
  56         let root = scopes.root_scope();
  57         scopes.add_params_bindings(body, root, &body.params);
  58         compute_expr_scopes(body.body_expr, body, &mut scopes, root);
  59         scopes
  60     }
  61
  62     pub fn entries(&self, scope: ScopeId) -> &[ScopeEntry] {
  63         &self.scopes[scope].entries
  64     }
  65
  66     /// If `scope` refers to a block expression scope, returns the corresponding `BlockId`.
  67     pub fn block(&self, scope: ScopeId) -> Option<BlockId> {
  68         self.scopes[scope].block
  69     }
  70
  71     /// If `scope` refers to a labeled expression scope, returns the corresponding `Label`.
  72     pub fn label(&self, scope: ScopeId) -> Option<(LabelId, Name)> {
  73         self.scopes[scope].label.clone()
  74     }
  75
  76     pub fn scope_chain(&self, scope: Option<ScopeId>) -> impl Iterator<Item = ScopeId> + '_ {
  77         std::iter::successors(scope, move |&scope| self.scopes[scope].parent)
  78     }
  79
  80     pub fn resolve_name_in_scope(&self, scope: ScopeId, name: &Name) -> Option<&ScopeEntry> {
  81         self.scope_chain(Some(scope))
  82             .find_map(|scope| self.entries(scope).iter().find(|it| it.name == *name))
  83     }
  84
  85     pub fn scope_for(&self, expr: ExprId) -> Option<ScopeId> {
  86         self.scope_by_expr.get(&expr).copied()
  87     }
  88
  89     pub fn scope_by_expr(&self) -> &FxHashMap<ExprId, ScopeId> {
  90         &self.scope_by_expr
  91     }
  92
  93     fn root_scope(&mut self) -> ScopeId {
  94         self.scopes.alloc(ScopeData { parent: None, block: None, label: None, entries: vec![] })
  95     }
  96
  97     fn new_scope(&mut self, parent: ScopeId) -> ScopeId {
  98         self.scopes.alloc(ScopeData {
  99             parent: Some(parent),
 100             block: None,
 101             label: None,
 102             entries: vec![],
 103         })
 104     }
 105
 106     fn new_labeled_scope(&mut self, parent: ScopeId, label: Option<(LabelId, Name)>) -> ScopeId {
 107         self.scopes.alloc(ScopeData { parent: Some(parent), block: None, label, entries: vec![] })
 108     }
 109
 110     fn new_block_scope(
 111         &mut self,
 112         parent: ScopeId,
 113         block: BlockId,
 114         label: Option<(LabelId, Name)>,
 115     ) -> ScopeId {
 116         self.scopes.alloc(ScopeData {
 117             parent: Some(parent),
 118             block: Some(block),
 119             label,
 120             entries: vec![],
 121         })
 122     }
 123
 124     fn add_bindings(&mut self, body: &Body, scope: ScopeId, pat: PatId) {
 125         let pattern = &body[pat];
 126         if let Pat::Bind { name, .. } = pattern {
 127             let entry = ScopeEntry { name: name.clone(), pat };
 128             self.scopes[scope].entries.push(entry);
 129         }
 130
 131         pattern.walk_child_pats(|pat| self.add_bindings(body, scope, pat));
 132     }
 133
 134     fn add_params_bindings(&mut self, body: &Body, scope: ScopeId, params: &[PatId]) {
 135         params.iter().for_each(|pat| self.add_bindings(body, scope, *pat));
 136     }
 137
 138     fn set_scope(&mut self, node: ExprId, scope: ScopeId) {
 139         self.scope_by_expr.insert(node, scope);
 140     }
 141 }
 142
 143 fn compute_block_scopes(
 144     statements: &[Statement],
 145     tail: Option<ExprId>,
 146     body: &Body,
 147     scopes: &mut ExprScopes,
 148     mut scope: ScopeId,
 149 ) {
 150     for stmt in statements {
 151         match stmt {
 152             Statement::Let { pat, initializer, else_branch, .. } => {
 153                 if let Some(expr) = initializer {
 154                     scopes.set_scope(*expr, scope);
 155                     compute_expr_scopes(*expr, body, scopes, scope);
 156                 }
 157                 if let Some(expr) = else_branch {
 158                     scopes.set_scope(*expr, scope);
 159                     compute_expr_scopes(*expr, body, scopes, scope);
 160                 }
 161                 scope = scopes.new_scope(scope);
 162                 scopes.add_bindings(body, scope, *pat);
 163             }
 164             Statement::Expr { expr, .. } => {
 165                 scopes.set_scope(*expr, scope);
 166                 compute_expr_scopes(*expr, body, scopes, scope);
 167             }
 168         }
 169     }
 170     if let Some(expr) = tail {
 171         compute_expr_scopes(expr, body, scopes, scope);
 172     }
 173 }
 174
 175 fn compute_expr_scopes(expr: ExprId, body: &Body, scopes: &mut ExprScopes, scope: ScopeId) {
 176     let make_label =
 177         |label: &Option<LabelId>| label.map(|label| (label, body.labels[label].name.clone()));
 178
 179     scopes.set_scope(expr, scope);
 180     match &body[expr] {
 181         Expr::Block { statements, tail, id, label } => {
 182             let scope = scopes.new_block_scope(scope, *id, make_label(label));
 183             // Overwrite the old scope for the block expr, so that every block scope can be found
 184             // via the block itself (important for blocks that only contain items, no expressions).
 185             scopes.set_scope(expr, scope);
 186             compute_block_scopes(statements, *tail, body, scopes, scope);
 187         }
 188         Expr::For { iterable, pat, body: body_expr, label } => {
 189             compute_expr_scopes(*iterable, body, scopes, scope);
 190             let scope = scopes.new_labeled_scope(scope, make_label(label));
 191             scopes.add_bindings(body, scope, *pat);
 192             compute_expr_scopes(*body_expr, body, scopes, scope);
 193         }
 194         Expr::While { condition, body: body_expr, label } => {
 195             let scope = scopes.new_labeled_scope(scope, make_label(label));
 196             compute_expr_scopes(*condition, body, scopes, scope);
 197             compute_expr_scopes(*body_expr, body, scopes, scope);
 198         }
 199         Expr::Loop { body: body_expr, label } => {
 200             let scope = scopes.new_labeled_scope(scope, make_label(label));
 201             compute_expr_scopes(*body_expr, body, scopes, scope);
 202         }
 203         Expr::Lambda { args, body: body_expr, .. } => {
 204             let scope = scopes.new_scope(scope);
 205             scopes.add_params_bindings(body, scope, args);
 206             compute_expr_scopes(*body_expr, body, scopes, scope);
 207         }
 208         Expr::Match { expr, arms } => {
 209             compute_expr_scopes(*expr, body, scopes, scope);
 210             for arm in arms {
 211                 let mut scope = scopes.new_scope(scope);
 212                 scopes.add_bindings(body, scope, arm.pat);
 213                 match arm.guard {
 214                     Some(MatchGuard::If { expr: guard }) => {
 215                         scopes.set_scope(guard, scope);
 216                         compute_expr_scopes(guard, body, scopes, scope);
 217                     }
 218                     Some(MatchGuard::IfLet { pat, expr: guard }) => {
 219                         scopes.set_scope(guard, scope);
 220                         compute_expr_scopes(guard, body, scopes, scope);
 221                         scope = scopes.new_scope(scope);
 222                         scopes.add_bindings(body, scope, pat);
 223                     }
 224                     _ => {}
 225                 };
 226                 scopes.set_scope(arm.expr, scope);
 227                 compute_expr_scopes(arm.expr, body, scopes, scope);
 228             }
 229         }
 230         e => e.walk_child_exprs(|e| compute_expr_scopes(e, body, scopes, scope)),
 231     };
 232 }
 233
 234 #[cfg(test)]
 235 mod tests {
 236     use base_db::{fixture::WithFixture, FileId, SourceDatabase};
 237     use hir_expand::{name::AsName, InFile};
 238     use syntax::{algo::find_node_at_offset, ast, AstNode};
 239     use test_utils::{assert_eq_text, extract_offset};
 240
 241     use crate::{db::DefDatabase, test_db::TestDB, FunctionId, ModuleDefId};
 242
 243     fn find_function(db: &TestDB, file_id: FileId) -> FunctionId {
 244         let krate = db.test_crate();
 245         let crate_def_map = db.crate_def_map(krate);
 246
 247         let module = crate_def_map.modules_for_file(file_id).next().unwrap();
 248         let (_, def) = crate_def_map[module].scope.entries().next().unwrap();
 249         match def.take_values().unwrap() {
 250             ModuleDefId::FunctionId(it) => it,
 251             _ => panic!(),
 252         }
 253     }
 254
 255     fn do_check(ra_fixture: &str, expected: &[&str]) {
 256         let (offset, code) = extract_offset(ra_fixture);
 257         let code = {
 258             let mut buf = String::new();
 259             let off: usize = offset.into();
 260             buf.push_str(&code[..off]);
 261             buf.push_str("$0marker");
 262             buf.push_str(&code[off..]);
 263             buf
 264         };
 265
 266         let (db, position) = TestDB::with_position(&code);
 267         let file_id = position.file_id;
 268         let offset = position.offset;
 269
 270         let file_syntax = db.parse(file_id).syntax_node();
 271         let marker: ast::PathExpr = find_node_at_offset(&file_syntax, offset).unwrap();
 272         let function = find_function(&db, file_id);
 273
 274         let scopes = db.expr_scopes(function.into());
 275         let (_body, source_map) = db.body_with_source_map(function.into());
 276
 277         let expr_id = source_map
 278             .node_expr(InFile { file_id: file_id.into(), value: &marker.into() })
 279             .unwrap();
 280         let scope = scopes.scope_for(expr_id);
 281
 282         let actual = scopes
 283             .scope_chain(scope)
 284             .flat_map(|scope| scopes.entries(scope))
 285             .map(|it| it.name().to_smol_str())
 286             .collect::<Vec<_>>()
 287             .join("\n");
 288         let expected = expected.join("\n");
 289         assert_eq_text!(&expected, &actual);
 290     }
 291
 292     #[test]
 293     fn test_lambda_scope() {
 294         do_check(
 295             r"
 296             fn quux(foo: i32) {
 297                 let f = |bar, baz: i32| {
 298                     $0
 299                 };
 300             }",
 301             &["bar", "baz", "foo"],
 302         );
 303     }
 304
 305     #[test]
 306     fn test_call_scope() {
 307         do_check(
 308             r"
 309             fn quux() {
 310                 f(|x| $0 );
 311             }",
 312             &["x"],
 313         );
 314     }
 315
 316     #[test]
 317     fn test_method_call_scope() {
 318         do_check(
 319             r"
 320             fn quux() {
 321                 z.f(|x| $0 );
 322             }",
 323             &["x"],
 324         );
 325     }
 326
 327     #[test]
 328     fn test_loop_scope() {
 329         do_check(
 330             r"
 331             fn quux() {
 332                 loop {
 333                     let x = ();
 334                     $0
 335                 };
 336             }",
 337             &["x"],
 338         );
 339     }
 340
 341     #[test]
 342     fn test_match() {
 343         do_check(
 344             r"
 345             fn quux() {
 346                 match () {
 347                     Some(x) => {
 348                         $0
 349                     }
 350                 };
 351             }",
 352             &["x"],
 353         );
 354     }
 355
 356     #[test]
 357     fn test_shadow_variable() {
 358         do_check(
 359             r"
 360             fn foo(x: String) {
 361                 let x : &str = &x$0;
 362             }",
 363             &["x"],
 364         );
 365     }
 366
 367     #[test]
 368     fn test_bindings_after_at() {
 369         do_check(
 370             r"
 371 fn foo() {
 372     match Some(()) {
 373         opt @ Some(unit) => {
 374             $0
 375         }
 376         _ => {}
 377     }
 378 }
 379 ",
 380             &["opt", "unit"],
 381         );
 382     }
 383
 384     #[test]
 385     fn macro_inner_item() {
 386         do_check(
 387             r"
 388             macro_rules! mac {
 389                 () => {{
 390                     fn inner() {}
 391                     inner();
 392                 }};
 393             }
 394
 395             fn foo() {
 396                 mac!();
 397                 $0
 398             }
 399         ",
 400             &[],
 401         );
 402     }
 403
 404     #[test]
 405     fn broken_inner_item() {
 406         do_check(
 407             r"
 408             fn foo() {
 409                 trait {}
 410                 $0
 411             }
 412         ",
 413             &[],
 414         );
 415     }
 416
 417     fn do_check_local_name(ra_fixture: &str, expected_offset: u32) {
 418         let (db, position) = TestDB::with_position(ra_fixture);
 419         let file_id = position.file_id;
 420         let offset = position.offset;
 421
 422         let file = db.parse(file_id).ok().unwrap();
 423         let expected_name = find_node_at_offset::<ast::Name>(file.syntax(), expected_offset.into())
 424             .expect("failed to find a name at the target offset");
 425         let name_ref: ast::NameRef = find_node_at_offset(file.syntax(), offset).unwrap();
 426
 427         let function = find_function(&db, file_id);
 428
 429         let scopes = db.expr_scopes(function.into());
 430         let (_body, source_map) = db.body_with_source_map(function.into());
 431
 432         let expr_scope = {
 433             let expr_ast = name_ref.syntax().ancestors().find_map(ast::Expr::cast).unwrap();
 434             let expr_id =
 435                 source_map.node_expr(InFile { file_id: file_id.into(), value: &expr_ast }).unwrap();
 436             scopes.scope_for(expr_id).unwrap()
 437         };
 438
 439         let resolved = scopes.resolve_name_in_scope(expr_scope, &name_ref.as_name()).unwrap();
 440         let pat_src = source_map.pat_syntax(resolved.pat()).unwrap();
 441
 442         let local_name = pat_src.value.either(
 443             |it| it.syntax_node_ptr().to_node(file.syntax()),
 444             |it| it.syntax_node_ptr().to_node(file.syntax()),
 445         );
 446         assert_eq!(local_name.text_range(), expected_name.syntax().text_range());
 447     }
 448
 449     #[test]
 450     fn test_resolve_local_name() {
 451         do_check_local_name(
 452             r#"
 453 fn foo(x: i32, y: u32) {
 454     {
 455         let z = x * 2;
 456     }
 457     {
 458         let t = x$0 * 3;
 459     }
 460 }
 461 "#,
 462             7,
 463         );
 464     }
 465
 466     #[test]
 467     fn test_resolve_local_name_declaration() {
 468         do_check_local_name(
 469             r#"
 470 fn foo(x: String) {
 471     let x : &str = &x$0;
 472 }
 473 "#,
 474             7,
 475         );
 476     }
 477
 478     #[test]
 479     fn test_resolve_local_name_shadow() {
 480         do_check_local_name(
 481             r"
 482 fn foo(x: String) {
 483     let x : &str = &x;
 484     x$0
 485 }
 486 ",
 487             28,
 488         );
 489     }
 490
 491     #[test]
 492     fn ref_patterns_contribute_bindings() {
 493         do_check_local_name(
 494             r"
 495 fn foo() {
 496     if let Some(&from) = bar() {
 497         from$0;
 498     }
 499 }
 500 ",
 501             28,
 502         );
 503     }
 504
 505     #[test]
 506     fn while_let_desugaring() {
 507         cov_mark::check!(infer_resolve_while_let);
 508         do_check_local_name(
 509             r#"
 510 fn test() {
 511     let foo: Option<f32> = None;
 512     while let Option::Some(spam) = foo {
 513         spam$0
 514     }
 515 }
 516 "#,
 517             75,
 518         );
 519     }
 520 }