diff options
Diffstat (limited to 'crates/ra_hir/src/module/nameres.rs')
-rw-r--r-- | crates/ra_hir/src/module/nameres.rs | 338 |
1 files changed, 338 insertions, 0 deletions
diff --git a/crates/ra_hir/src/module/nameres.rs b/crates/ra_hir/src/module/nameres.rs new file mode 100644 index 000000000..837a8d5ae --- /dev/null +++ b/crates/ra_hir/src/module/nameres.rs | |||
@@ -0,0 +1,338 @@ | |||
1 | //! Name resolution algorithm. The end result of the algorithm is `ItemMap`: a | ||
2 | //! map with maps each module to it's scope: the set of items, visible in the | ||
3 | //! module. That is, we only resolve imports here, name resolution of item | ||
4 | //! bodies will be done in a separate step. | ||
5 | //! | ||
6 | //! Like Rustc, we use an interative per-crate algorithm: we start with scopes | ||
7 | //! containing only directly defined items, and then iteratively resolve | ||
8 | //! imports. | ||
9 | //! | ||
10 | //! To make this work nicely in the IDE scenarios, we place `InputModuleItems` | ||
11 | //! in between raw syntax and name resolution. `InputModuleItems` are computed | ||
12 | //! using only the module's syntax, and it is all directly defined items plus | ||
13 | //! imports. The plain is to make `InputModuleItems` independent of local | ||
14 | //! modifications (that is, typing inside a function shold not change IMIs), | ||
15 | //! such that the results of name resolution can be preserved unless the module | ||
16 | //! structure itself is modified. | ||
17 | use std::{ | ||
18 | sync::Arc, | ||
19 | }; | ||
20 | |||
21 | use rustc_hash::FxHashMap; | ||
22 | use ra_syntax::{ | ||
23 | TextRange, | ||
24 | SmolStr, SyntaxKind::{self, *}, | ||
25 | ast::{self, AstNode} | ||
26 | }; | ||
27 | use ra_db::SourceRootId; | ||
28 | |||
29 | use crate::{ | ||
30 | Cancelable, FileId, | ||
31 | DefId, DefLoc, | ||
32 | SourceItemId, SourceFileItemId, SourceFileItems, | ||
33 | Path, PathKind, | ||
34 | HirDatabase, | ||
35 | module::{ModuleId, ModuleTree}, | ||
36 | }; | ||
37 | |||
38 | /// Item map is the result of the name resolution. Item map contains, for each | ||
39 | /// module, the set of visible items. | ||
40 | #[derive(Default, Debug, PartialEq, Eq)] | ||
41 | pub struct ItemMap { | ||
42 | pub per_module: FxHashMap<ModuleId, ModuleScope>, | ||
43 | } | ||
44 | |||
45 | #[derive(Debug, Default, PartialEq, Eq, Clone)] | ||
46 | pub struct ModuleScope { | ||
47 | pub items: FxHashMap<SmolStr, Resolution>, | ||
48 | } | ||
49 | |||
50 | impl ModuleScope { | ||
51 | pub fn entries<'a>(&'a self) -> impl Iterator<Item = (&'a SmolStr, &Resolution)> + 'a { | ||
52 | self.items.iter() | ||
53 | } | ||
54 | pub fn get(&self, name: &SmolStr) -> Option<&Resolution> { | ||
55 | self.items.get(name) | ||
56 | } | ||
57 | } | ||
58 | |||
59 | /// A set of items and imports declared inside a module, without relation to | ||
60 | /// other modules. | ||
61 | /// | ||
62 | /// This stands in-between raw syntax and name resolution and alow us to avoid | ||
63 | /// recomputing name res: if `InputModuleItems` are the same, we can avoid | ||
64 | /// running name resolution. | ||
65 | #[derive(Debug, Default, PartialEq, Eq)] | ||
66 | pub struct InputModuleItems { | ||
67 | items: Vec<ModuleItem>, | ||
68 | imports: Vec<Import>, | ||
69 | } | ||
70 | |||
71 | #[derive(Debug, PartialEq, Eq)] | ||
72 | struct ModuleItem { | ||
73 | id: SourceFileItemId, | ||
74 | name: SmolStr, | ||
75 | kind: SyntaxKind, | ||
76 | vis: Vis, | ||
77 | } | ||
78 | |||
79 | #[derive(Debug, PartialEq, Eq)] | ||
80 | enum Vis { | ||
81 | // Priv, | ||
82 | Other, | ||
83 | } | ||
84 | |||
85 | #[derive(Debug, Clone, PartialEq, Eq)] | ||
86 | struct Import { | ||
87 | path: Path, | ||
88 | kind: ImportKind, | ||
89 | } | ||
90 | |||
91 | #[derive(Debug, Clone, Copy, PartialEq, Eq)] | ||
92 | pub struct NamedImport { | ||
93 | pub file_item_id: SourceFileItemId, | ||
94 | pub relative_range: TextRange, | ||
95 | } | ||
96 | |||
97 | impl NamedImport { | ||
98 | pub fn range(&self, db: &impl HirDatabase, file_id: FileId) -> TextRange { | ||
99 | let source_item_id = SourceItemId { | ||
100 | file_id, | ||
101 | item_id: self.file_item_id, | ||
102 | }; | ||
103 | let syntax = db.file_item(source_item_id); | ||
104 | let offset = syntax.borrowed().range().start(); | ||
105 | self.relative_range + offset | ||
106 | } | ||
107 | } | ||
108 | |||
109 | #[derive(Debug, Clone, PartialEq, Eq)] | ||
110 | enum ImportKind { | ||
111 | Glob, | ||
112 | Named(NamedImport), | ||
113 | } | ||
114 | |||
115 | /// Resolution is basically `DefId` atm, but it should account for stuff like | ||
116 | /// multiple namespaces, ambiguity and errors. | ||
117 | #[derive(Debug, Clone, PartialEq, Eq)] | ||
118 | pub struct Resolution { | ||
119 | /// None for unresolved | ||
120 | pub def_id: Option<DefId>, | ||
121 | /// ident by whitch this is imported into local scope. | ||
122 | pub import: Option<NamedImport>, | ||
123 | } | ||
124 | |||
125 | // #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] | ||
126 | // enum Namespace { | ||
127 | // Types, | ||
128 | // Values, | ||
129 | // } | ||
130 | |||
131 | // #[derive(Debug)] | ||
132 | // struct PerNs<T> { | ||
133 | // types: Option<T>, | ||
134 | // values: Option<T>, | ||
135 | // } | ||
136 | |||
137 | impl InputModuleItems { | ||
138 | pub(crate) fn new<'a>( | ||
139 | file_items: &SourceFileItems, | ||
140 | items: impl Iterator<Item = ast::ModuleItem<'a>>, | ||
141 | ) -> InputModuleItems { | ||
142 | let mut res = InputModuleItems::default(); | ||
143 | for item in items { | ||
144 | res.add_item(file_items, item); | ||
145 | } | ||
146 | res | ||
147 | } | ||
148 | |||
149 | fn add_item(&mut self, file_items: &SourceFileItems, item: ast::ModuleItem) -> Option<()> { | ||
150 | match item { | ||
151 | ast::ModuleItem::StructDef(it) => self.items.push(ModuleItem::new(file_items, it)?), | ||
152 | ast::ModuleItem::EnumDef(it) => self.items.push(ModuleItem::new(file_items, it)?), | ||
153 | ast::ModuleItem::FnDef(it) => self.items.push(ModuleItem::new(file_items, it)?), | ||
154 | ast::ModuleItem::TraitDef(it) => self.items.push(ModuleItem::new(file_items, it)?), | ||
155 | ast::ModuleItem::TypeDef(it) => self.items.push(ModuleItem::new(file_items, it)?), | ||
156 | ast::ModuleItem::ImplItem(_) => { | ||
157 | // impls don't define items | ||
158 | } | ||
159 | ast::ModuleItem::UseItem(it) => self.add_use_item(file_items, it), | ||
160 | ast::ModuleItem::ExternCrateItem(_) => { | ||
161 | // TODO | ||
162 | } | ||
163 | ast::ModuleItem::ConstDef(it) => self.items.push(ModuleItem::new(file_items, it)?), | ||
164 | ast::ModuleItem::StaticDef(it) => self.items.push(ModuleItem::new(file_items, it)?), | ||
165 | ast::ModuleItem::Module(it) => self.items.push(ModuleItem::new(file_items, it)?), | ||
166 | } | ||
167 | Some(()) | ||
168 | } | ||
169 | |||
170 | fn add_use_item(&mut self, file_items: &SourceFileItems, item: ast::UseItem) { | ||
171 | let file_item_id = file_items.id_of(item.syntax()); | ||
172 | let start_offset = item.syntax().range().start(); | ||
173 | Path::expand_use_item(item, |path, range| { | ||
174 | let kind = match range { | ||
175 | None => ImportKind::Glob, | ||
176 | Some(range) => ImportKind::Named(NamedImport { | ||
177 | file_item_id, | ||
178 | relative_range: range - start_offset, | ||
179 | }), | ||
180 | }; | ||
181 | self.imports.push(Import { kind, path }) | ||
182 | }) | ||
183 | } | ||
184 | } | ||
185 | |||
186 | impl ModuleItem { | ||
187 | fn new<'a>(file_items: &SourceFileItems, item: impl ast::NameOwner<'a>) -> Option<ModuleItem> { | ||
188 | let name = item.name()?.text(); | ||
189 | let kind = item.syntax().kind(); | ||
190 | let vis = Vis::Other; | ||
191 | let id = file_items.id_of(item.syntax()); | ||
192 | let res = ModuleItem { | ||
193 | id, | ||
194 | name, | ||
195 | kind, | ||
196 | vis, | ||
197 | }; | ||
198 | Some(res) | ||
199 | } | ||
200 | } | ||
201 | |||
202 | pub(crate) struct Resolver<'a, DB> { | ||
203 | pub db: &'a DB, | ||
204 | pub input: &'a FxHashMap<ModuleId, Arc<InputModuleItems>>, | ||
205 | pub source_root: SourceRootId, | ||
206 | pub module_tree: Arc<ModuleTree>, | ||
207 | pub result: ItemMap, | ||
208 | } | ||
209 | |||
210 | impl<'a, DB> Resolver<'a, DB> | ||
211 | where | ||
212 | DB: HirDatabase, | ||
213 | { | ||
214 | pub(crate) fn resolve(mut self) -> Cancelable<ItemMap> { | ||
215 | for (&module_id, items) in self.input.iter() { | ||
216 | self.populate_module(module_id, items) | ||
217 | } | ||
218 | |||
219 | for &module_id in self.input.keys() { | ||
220 | self.db.check_canceled()?; | ||
221 | self.resolve_imports(module_id); | ||
222 | } | ||
223 | Ok(self.result) | ||
224 | } | ||
225 | |||
226 | fn populate_module(&mut self, module_id: ModuleId, input: &InputModuleItems) { | ||
227 | let file_id = module_id.source(&self.module_tree).file_id(); | ||
228 | |||
229 | let mut module_items = ModuleScope::default(); | ||
230 | |||
231 | for import in input.imports.iter() { | ||
232 | if let Some(name) = import.path.segments.iter().last() { | ||
233 | if let ImportKind::Named(import) = import.kind { | ||
234 | module_items.items.insert( | ||
235 | name.clone(), | ||
236 | Resolution { | ||
237 | def_id: None, | ||
238 | import: Some(import), | ||
239 | }, | ||
240 | ); | ||
241 | } | ||
242 | } | ||
243 | } | ||
244 | |||
245 | for item in input.items.iter() { | ||
246 | if item.kind == MODULE { | ||
247 | // handle submodules separatelly | ||
248 | continue; | ||
249 | } | ||
250 | let def_loc = DefLoc::Item { | ||
251 | source_item_id: SourceItemId { | ||
252 | file_id, | ||
253 | item_id: item.id, | ||
254 | }, | ||
255 | }; | ||
256 | let def_id = def_loc.id(self.db); | ||
257 | let resolution = Resolution { | ||
258 | def_id: Some(def_id), | ||
259 | import: None, | ||
260 | }; | ||
261 | module_items.items.insert(item.name.clone(), resolution); | ||
262 | } | ||
263 | |||
264 | for (name, mod_id) in module_id.children(&self.module_tree) { | ||
265 | let def_loc = DefLoc::Module { | ||
266 | id: mod_id, | ||
267 | source_root: self.source_root, | ||
268 | }; | ||
269 | let def_id = def_loc.id(self.db); | ||
270 | let resolution = Resolution { | ||
271 | def_id: Some(def_id), | ||
272 | import: None, | ||
273 | }; | ||
274 | module_items.items.insert(name, resolution); | ||
275 | } | ||
276 | |||
277 | self.result.per_module.insert(module_id, module_items); | ||
278 | } | ||
279 | |||
280 | fn resolve_imports(&mut self, module_id: ModuleId) { | ||
281 | for import in self.input[&module_id].imports.iter() { | ||
282 | self.resolve_import(module_id, import); | ||
283 | } | ||
284 | } | ||
285 | |||
286 | fn resolve_import(&mut self, module_id: ModuleId, import: &Import) { | ||
287 | let ptr = match import.kind { | ||
288 | ImportKind::Glob => return, | ||
289 | ImportKind::Named(ptr) => ptr, | ||
290 | }; | ||
291 | |||
292 | let mut curr = match import.path.kind { | ||
293 | // TODO: handle extern crates | ||
294 | PathKind::Plain => return, | ||
295 | PathKind::Self_ => module_id, | ||
296 | PathKind::Super => { | ||
297 | match module_id.parent(&self.module_tree) { | ||
298 | Some(it) => it, | ||
299 | // TODO: error | ||
300 | None => return, | ||
301 | } | ||
302 | } | ||
303 | PathKind::Crate => module_id.crate_root(&self.module_tree), | ||
304 | }; | ||
305 | |||
306 | for (i, name) in import.path.segments.iter().enumerate() { | ||
307 | let is_last = i == import.path.segments.len() - 1; | ||
308 | |||
309 | let def_id = match self.result.per_module[&curr].items.get(name) { | ||
310 | None => return, | ||
311 | Some(res) => match res.def_id { | ||
312 | Some(it) => it, | ||
313 | None => return, | ||
314 | }, | ||
315 | }; | ||
316 | |||
317 | if !is_last { | ||
318 | curr = match def_id.loc(self.db) { | ||
319 | DefLoc::Module { id, .. } => id, | ||
320 | _ => return, | ||
321 | } | ||
322 | } else { | ||
323 | self.update(module_id, |items| { | ||
324 | let res = Resolution { | ||
325 | def_id: Some(def_id), | ||
326 | import: Some(ptr), | ||
327 | }; | ||
328 | items.items.insert(name.clone(), res); | ||
329 | }) | ||
330 | } | ||
331 | } | ||
332 | } | ||
333 | |||
334 | fn update(&mut self, module_id: ModuleId, f: impl FnOnce(&mut ModuleScope)) { | ||
335 | let module_items = self.result.per_module.get_mut(&module_id).unwrap(); | ||
336 | f(module_items) | ||
337 | } | ||
338 | } | ||