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