aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir_def/src
diff options
context:
space:
mode:
authorEdwin Cheng <[email protected]>2019-12-07 11:20:41 +0000
committerEdwin Cheng <[email protected]>2019-12-07 11:24:15 +0000
commit51f4fb448f1993a20c9527a8e6d301a9202ce35a (patch)
tree112fe280ceeb3d27d79ff79f31aabae170aafd78 /crates/ra_hir_def/src
parente5997e174666435acd5abb4531f833bd41bbdb00 (diff)
Refactor resolve_imports logic
Diffstat (limited to 'crates/ra_hir_def/src')
-rw-r--r--crates/ra_hir_def/src/nameres/collector.rs156
-rw-r--r--crates/ra_hir_def/src/nameres/path_resolution.rs13
2 files changed, 129 insertions, 40 deletions
diff --git a/crates/ra_hir_def/src/nameres/collector.rs b/crates/ra_hir_def/src/nameres/collector.rs
index 252178b6b..3b3f30eec 100644
--- a/crates/ra_hir_def/src/nameres/collector.rs
+++ b/crates/ra_hir_def/src/nameres/collector.rs
@@ -58,6 +58,8 @@ pub(super) fn collect_defs(db: &impl DefDatabase, mut def_map: CrateDefMap) -> C
58 def_map, 58 def_map,
59 glob_imports: FxHashMap::default(), 59 glob_imports: FxHashMap::default(),
60 unresolved_imports: Vec::new(), 60 unresolved_imports: Vec::new(),
61 resolved_imports: Vec::new(),
62
61 unexpanded_macros: Vec::new(), 63 unexpanded_macros: Vec::new(),
62 unexpanded_attribute_macros: Vec::new(), 64 unexpanded_attribute_macros: Vec::new(),
63 mod_dirs: FxHashMap::default(), 65 mod_dirs: FxHashMap::default(),
@@ -97,12 +99,41 @@ impl MacroStackMonitor {
97 } 99 }
98} 100}
99 101
102#[derive(Copy, Clone, Debug, Eq, PartialEq)]
103enum PartialResolvedImport {
104 /// None of any namespaces is resolved
105 Unresolved,
106 /// One of namespaces is resolved
107 Indeterminate(PerNs),
108 /// All namespaces are resolved, OR it is came from other crate
109 Resolved(PerNs),
110}
111
112impl PartialResolvedImport {
113 fn namespaces(&self) -> PerNs {
114 match self {
115 PartialResolvedImport::Unresolved => PerNs::none(),
116 PartialResolvedImport::Indeterminate(ns) => *ns,
117 PartialResolvedImport::Resolved(ns) => *ns,
118 }
119 }
120}
121
122#[derive(Clone, Debug, Eq, PartialEq)]
123struct ImportDirective {
124 module_id: LocalModuleId,
125 import_id: LocalImportId,
126 import: raw::ImportData,
127 status: PartialResolvedImport,
128}
129
100/// Walks the tree of module recursively 130/// Walks the tree of module recursively
101struct DefCollector<'a, DB> { 131struct DefCollector<'a, DB> {
102 db: &'a DB, 132 db: &'a DB,
103 def_map: CrateDefMap, 133 def_map: CrateDefMap,
104 glob_imports: FxHashMap<LocalModuleId, Vec<(LocalModuleId, LocalImportId)>>, 134 glob_imports: FxHashMap<LocalModuleId, Vec<(LocalModuleId, LocalImportId)>>,
105 unresolved_imports: Vec<(LocalModuleId, LocalImportId, raw::ImportData)>, 135 unresolved_imports: Vec<ImportDirective>,
136 resolved_imports: Vec<ImportDirective>,
106 unexpanded_macros: Vec<(LocalModuleId, AstId<ast::MacroCall>, Path)>, 137 unexpanded_macros: Vec<(LocalModuleId, AstId<ast::MacroCall>, Path)>,
107 unexpanded_attribute_macros: Vec<(LocalModuleId, AstId<ast::ModuleItem>, Path)>, 138 unexpanded_attribute_macros: Vec<(LocalModuleId, AstId<ast::ModuleItem>, Path)>,
108 mod_dirs: FxHashMap<LocalModuleId, ModDir>, 139 mod_dirs: FxHashMap<LocalModuleId, ModDir>,
@@ -148,9 +179,11 @@ where
148 let mut i = 0; 179 let mut i = 0;
149 loop { 180 loop {
150 self.db.check_canceled(); 181 self.db.check_canceled();
151 match (self.resolve_imports(), self.resolve_macros()) { 182 self.resolve_imports();
152 (ReachedFixedPoint::Yes, ReachedFixedPoint::Yes) => break, 183
153 _ => i += 1, 184 match self.resolve_macros() {
185 ReachedFixedPoint::Yes => break,
186 ReachedFixedPoint::No => i += 1,
154 } 187 }
155 if i == 1000 { 188 if i == 1000 {
156 log::error!("name resolution is stuck"); 189 log::error!("name resolution is stuck");
@@ -158,10 +191,26 @@ where
158 } 191 }
159 } 192 }
160 193
194 // Resolve all indeterminate resolved imports again
195 // As some of the macros will expand newly import shadowing partial resolved imports
196 // FIXME: We maybe could skip this, if we handle the Indetermine imports in `resolve_imports`
197 // correctly
198 let partial_resolved = self.resolved_imports.iter().filter_map(|directive| {
199 if let PartialResolvedImport::Indeterminate(_) = directive.status {
200 let mut directive = directive.clone();
201 directive.status = PartialResolvedImport::Unresolved;
202 Some(directive)
203 } else {
204 None
205 }
206 });
207 self.unresolved_imports.extend(partial_resolved);
208 self.resolve_imports();
209
161 let unresolved_imports = std::mem::replace(&mut self.unresolved_imports, Vec::new()); 210 let unresolved_imports = std::mem::replace(&mut self.unresolved_imports, Vec::new());
162 // show unresolved imports in completion, etc 211 // show unresolved imports in completion, etc
163 for (module_id, import, import_data) in unresolved_imports { 212 for directive in unresolved_imports {
164 self.record_resolved_import(module_id, PerNs::none(), import, &import_data) 213 self.record_resolved_import(&directive)
165 } 214 }
166 } 215 }
167 216
@@ -262,31 +311,43 @@ where
262 } 311 }
263 } 312 }
264 313
265 fn resolve_imports(&mut self) -> ReachedFixedPoint { 314 /// Import resolution
266 let mut imports = std::mem::replace(&mut self.unresolved_imports, Vec::new()); 315 ///
267 let mut resolved = Vec::new(); 316 /// This is a fix point algorithm. We resolve imports until no forward
268 imports.retain(|(module_id, import, import_data)| { 317 /// progress in resolving imports is made
269 let (def, fp) = self.resolve_import(*module_id, import_data); 318 fn resolve_imports(&mut self) {
270 if fp == ReachedFixedPoint::Yes { 319 let mut n_previous_unresolved = self.unresolved_imports.len() + 1;
271 resolved.push((*module_id, def, *import, import_data.clone())) 320
321 while self.unresolved_imports.len() < n_previous_unresolved {
322 n_previous_unresolved = self.unresolved_imports.len();
323 let imports = std::mem::replace(&mut self.unresolved_imports, Vec::new());
324 for mut directive in imports {
325 directive.status = self.resolve_import(directive.module_id, &directive.import);
326
327 match directive.status {
328 PartialResolvedImport::Indeterminate(_) => {
329 self.record_resolved_import(&directive);
330 // FIXME: For avoid performance regression,
331 // we consider an imported resolved if it is indeterminate (i.e not all namespace resolved)
332 self.resolved_imports.push(directive)
333 }
334 PartialResolvedImport::Resolved(_) => {
335 self.record_resolved_import(&directive);
336 self.resolved_imports.push(directive)
337 }
338 PartialResolvedImport::Unresolved => {
339 self.unresolved_imports.push(directive);
340 }
341 }
272 } 342 }
273 fp == ReachedFixedPoint::No
274 });
275 self.unresolved_imports = imports;
276 // Resolves imports, filling-in module scopes
277 let result =
278 if resolved.is_empty() { ReachedFixedPoint::Yes } else { ReachedFixedPoint::No };
279 for (module_id, def, import, import_data) in resolved {
280 self.record_resolved_import(module_id, def, import, &import_data)
281 } 343 }
282 result
283 } 344 }
284 345
285 fn resolve_import( 346 fn resolve_import(
286 &self, 347 &self,
287 module_id: LocalModuleId, 348 module_id: LocalModuleId,
288 import: &raw::ImportData, 349 import: &raw::ImportData,
289 ) -> (PerNs, ReachedFixedPoint) { 350 ) -> PartialResolvedImport {
290 log::debug!("resolving import: {:?} ({:?})", import, self.def_map.edition); 351 log::debug!("resolving import: {:?} ({:?})", import, self.def_map.edition);
291 if import.is_extern_crate { 352 if import.is_extern_crate {
292 let res = self.def_map.resolve_name_in_extern_prelude( 353 let res = self.def_map.resolve_name_in_extern_prelude(
@@ -295,7 +356,7 @@ where
295 .as_ident() 356 .as_ident()
296 .expect("extern crate should have been desugared to one-element path"), 357 .expect("extern crate should have been desugared to one-element path"),
297 ); 358 );
298 (res, ReachedFixedPoint::Yes) 359 PartialResolvedImport::Resolved(res)
299 } else { 360 } else {
300 let res = self.def_map.resolve_path_fp_with_macro( 361 let res = self.def_map.resolve_path_fp_with_macro(
301 self.db, 362 self.db,
@@ -305,17 +366,35 @@ where
305 BuiltinShadowMode::Module, 366 BuiltinShadowMode::Module,
306 ); 367 );
307 368
308 (res.resolved_def, res.reached_fixedpoint) 369 let def = res.resolved_def;
370 if res.reached_fixedpoint == ReachedFixedPoint::No {
371 return PartialResolvedImport::Unresolved;
372 }
373
374 if let Some(krate) = res.krate {
375 if krate != self.def_map.krate {
376 return PartialResolvedImport::Resolved(def);
377 }
378 }
379
380 // Check whether all namespace is resolved
381 if def.take_types().is_some()
382 && def.take_values().is_some()
383 && def.take_macros().is_some()
384 {
385 PartialResolvedImport::Resolved(def)
386 } else {
387 PartialResolvedImport::Indeterminate(def)
388 }
309 } 389 }
310 } 390 }
311 391
312 fn record_resolved_import( 392 fn record_resolved_import(&mut self, directive: &ImportDirective) {
313 &mut self, 393 let module_id = directive.module_id;
314 module_id: LocalModuleId, 394 let import_id = directive.import_id;
315 def: PerNs, 395 let import = &directive.import;
316 import_id: LocalImportId, 396 let def = directive.status.namespaces();
317 import: &raw::ImportData, 397
318 ) {
319 if import.is_glob { 398 if import.is_glob {
320 log::debug!("glob import: {:?}", import); 399 log::debug!("glob import: {:?}", import);
321 match def.take_types() { 400 match def.take_types() {
@@ -615,10 +694,14 @@ where
615 raw::RawItemKind::Module(m) => { 694 raw::RawItemKind::Module(m) => {
616 self.collect_module(&self.raw_items[m], &item.attrs) 695 self.collect_module(&self.raw_items[m], &item.attrs)
617 } 696 }
618 raw::RawItemKind::Import(import_id) => self 697 raw::RawItemKind::Import(import_id) => {
619 .def_collector 698 self.def_collector.unresolved_imports.push(ImportDirective {
620 .unresolved_imports 699 module_id: self.module_id,
621 .push((self.module_id, import_id, self.raw_items[import_id].clone())), 700 import_id,
701 import: self.raw_items[import_id].clone(),
702 status: PartialResolvedImport::Unresolved,
703 })
704 }
622 raw::RawItemKind::Def(def) => { 705 raw::RawItemKind::Def(def) => {
623 self.define_def(&self.raw_items[def], &item.attrs) 706 self.define_def(&self.raw_items[def], &item.attrs)
624 } 707 }
@@ -886,6 +969,7 @@ mod tests {
886 def_map, 969 def_map,
887 glob_imports: FxHashMap::default(), 970 glob_imports: FxHashMap::default(),
888 unresolved_imports: Vec::new(), 971 unresolved_imports: Vec::new(),
972 resolved_imports: Vec::new(),
889 unexpanded_macros: Vec::new(), 973 unexpanded_macros: Vec::new(),
890 unexpanded_attribute_macros: Vec::new(), 974 unexpanded_attribute_macros: Vec::new(),
891 mod_dirs: FxHashMap::default(), 975 mod_dirs: FxHashMap::default(),
diff --git a/crates/ra_hir_def/src/nameres/path_resolution.rs b/crates/ra_hir_def/src/nameres/path_resolution.rs
index 42a75226b..aab4b1dd9 100644
--- a/crates/ra_hir_def/src/nameres/path_resolution.rs
+++ b/crates/ra_hir_def/src/nameres/path_resolution.rs
@@ -19,7 +19,7 @@ use crate::{
19 nameres::{BuiltinShadowMode, CrateDefMap}, 19 nameres::{BuiltinShadowMode, CrateDefMap},
20 path::{Path, PathKind}, 20 path::{Path, PathKind},
21 per_ns::PerNs, 21 per_ns::PerNs,
22 AdtId, EnumVariantId, LocalModuleId, ModuleDefId, ModuleId, 22 AdtId, CrateId, EnumVariantId, LocalModuleId, ModuleDefId, ModuleId,
23}; 23};
24 24
25#[derive(Debug, Clone, Copy, PartialEq, Eq)] 25#[derive(Debug, Clone, Copy, PartialEq, Eq)]
@@ -39,19 +39,21 @@ pub(super) struct ResolvePathResult {
39 pub(super) resolved_def: PerNs, 39 pub(super) resolved_def: PerNs,
40 pub(super) segment_index: Option<usize>, 40 pub(super) segment_index: Option<usize>,
41 pub(super) reached_fixedpoint: ReachedFixedPoint, 41 pub(super) reached_fixedpoint: ReachedFixedPoint,
42 pub(super) krate: Option<CrateId>,
42} 43}
43 44
44impl ResolvePathResult { 45impl ResolvePathResult {
45 fn empty(reached_fixedpoint: ReachedFixedPoint) -> ResolvePathResult { 46 fn empty(reached_fixedpoint: ReachedFixedPoint) -> ResolvePathResult {
46 ResolvePathResult::with(PerNs::none(), reached_fixedpoint, None) 47 ResolvePathResult::with(PerNs::none(), reached_fixedpoint, None, None)
47 } 48 }
48 49
49 fn with( 50 fn with(
50 resolved_def: PerNs, 51 resolved_def: PerNs,
51 reached_fixedpoint: ReachedFixedPoint, 52 reached_fixedpoint: ReachedFixedPoint,
52 segment_index: Option<usize>, 53 segment_index: Option<usize>,
54 krate: Option<CrateId>,
53 ) -> ResolvePathResult { 55 ) -> ResolvePathResult {
54 ResolvePathResult { resolved_def, reached_fixedpoint, segment_index } 56 ResolvePathResult { resolved_def, reached_fixedpoint, segment_index, krate }
55 } 57 }
56} 58}
57 59
@@ -175,6 +177,7 @@ impl CrateDefMap {
175 def, 177 def,
176 ReachedFixedPoint::Yes, 178 ReachedFixedPoint::Yes,
177 s.map(|s| s + i), 179 s.map(|s| s + i),
180 Some(module.krate),
178 ); 181 );
179 } 182 }
180 183
@@ -201,6 +204,7 @@ impl CrateDefMap {
201 PerNs::types(e.into()), 204 PerNs::types(e.into()),
202 ReachedFixedPoint::Yes, 205 ReachedFixedPoint::Yes,
203 Some(i), 206 Some(i),
207 Some(self.krate),
204 ); 208 );
205 } 209 }
206 } 210 }
@@ -218,12 +222,13 @@ impl CrateDefMap {
218 PerNs::types(s), 222 PerNs::types(s),
219 ReachedFixedPoint::Yes, 223 ReachedFixedPoint::Yes,
220 Some(i), 224 Some(i),
225 Some(self.krate),
221 ); 226 );
222 } 227 }
223 }; 228 };
224 } 229 }
225 230
226 ResolvePathResult::with(curr_per_ns, ReachedFixedPoint::Yes, None) 231 ResolvePathResult::with(curr_per_ns, ReachedFixedPoint::Yes, None, Some(self.krate))
227 } 232 }
228 233
229 fn resolve_name_in_module( 234 fn resolve_name_in_module(