aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_def/src/import_map.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/hir_def/src/import_map.rs')
-rw-r--r--crates/hir_def/src/import_map.rs169
1 files changed, 87 insertions, 82 deletions
diff --git a/crates/hir_def/src/import_map.rs b/crates/hir_def/src/import_map.rs
index 960cabb5f..404e3e153 100644
--- a/crates/hir_def/src/import_map.rs
+++ b/crates/hir_def/src/import_map.rs
@@ -1,6 +1,6 @@
1//! A map of all publicly exported items in a crate. 1//! A map of all publicly exported items in a crate.
2 2
3use std::{cmp::Ordering, fmt, hash::BuildHasherDefault, sync::Arc}; 3use std::{fmt, hash::BuildHasherDefault, sync::Arc};
4 4
5use base_db::CrateId; 5use base_db::CrateId;
6use fst::{self, Streamer}; 6use fst::{self, Streamer};
@@ -69,81 +69,11 @@ pub struct ImportMap {
69impl ImportMap { 69impl ImportMap {
70 pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> { 70 pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> {
71 let _p = profile::span("import_map_query"); 71 let _p = profile::span("import_map_query");
72 let def_map = db.crate_def_map(krate);
73 let mut import_map = Self::default();
74
75 // We look only into modules that are public(ly reexported), starting with the crate root.
76 let empty = ImportPath { segments: vec![] };
77 let root = def_map.module_id(def_map.root());
78 let mut worklist = vec![(root, empty)];
79 while let Some((module, mod_path)) = worklist.pop() {
80 let ext_def_map;
81 let mod_data = if module.krate == krate {
82 &def_map[module.local_id]
83 } else {
84 // The crate might reexport a module defined in another crate.
85 ext_def_map = module.def_map(db);
86 &ext_def_map[module.local_id]
87 };
88
89 let visible_items = mod_data.scope.entries().filter_map(|(name, per_ns)| {
90 let per_ns = per_ns.filter_visibility(|vis| vis == Visibility::Public);
91 if per_ns.is_none() {
92 None
93 } else {
94 Some((name, per_ns))
95 }
96 });
97
98 for (name, per_ns) in visible_items {
99 let mk_path = || {
100 let mut path = mod_path.clone();
101 path.segments.push(name.clone());
102 path
103 };
104
105 for item in per_ns.iter_items() {
106 let path = mk_path();
107 let path_len = path.len();
108 let import_info =
109 ImportInfo { path, container: module, is_trait_assoc_item: false };
110
111 if let Some(ModuleDefId::TraitId(tr)) = item.as_module_def_id() {
112 import_map.collect_trait_assoc_items(
113 db,
114 tr,
115 matches!(item, ItemInNs::Types(_)),
116 &import_info,
117 );
118 }
119 72
120 match import_map.map.entry(item) { 73 let mut import_map = collect_import_map(db, krate);
121 Entry::Vacant(entry) => {
122 entry.insert(import_info);
123 }
124 Entry::Occupied(mut entry) => {
125 // If the new path is shorter, prefer that one.
126 if path_len < entry.get().path.len() {
127 *entry.get_mut() = import_info;
128 } else {
129 continue;
130 }
131 }
132 }
133
134 // If we've just added a path to a module, descend into it. We might traverse
135 // modules multiple times, but only if the new path to it is shorter than the
136 // first (else we `continue` above).
137 if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
138 worklist.push((mod_id, mk_path()));
139 }
140 }
141 }
142 }
143 74
144 let mut importables = import_map.map.iter().collect::<Vec<_>>(); 75 let mut importables = import_map.map.iter().collect::<Vec<_>>();
145 76 importables.sort_by_cached_key(|(_, import_info)| fst_path(&import_info.path));
146 importables.sort_by(cmp);
147 77
148 // Build the FST, taking care not to insert duplicate values. 78 // Build the FST, taking care not to insert duplicate values.
149 79
@@ -151,13 +81,13 @@ impl ImportMap {
151 let mut last_batch_start = 0; 81 let mut last_batch_start = 0;
152 82
153 for idx in 0..importables.len() { 83 for idx in 0..importables.len() {
154 if let Some(next_item) = importables.get(idx + 1) { 84 let key = fst_path(&importables[last_batch_start].1.path);
155 if cmp(&importables[last_batch_start], next_item) == Ordering::Equal { 85 if let Some((_, next_import_info)) = importables.get(idx + 1) {
86 if key == fst_path(&next_import_info.path) {
156 continue; 87 continue;
157 } 88 }
158 } 89 }
159 90
160 let key = fst_path(&importables[last_batch_start].1.path);
161 builder.insert(key, last_batch_start as u64).unwrap(); 91 builder.insert(key, last_batch_start as u64).unwrap();
162 92
163 last_batch_start = idx + 1; 93 last_batch_start = idx + 1;
@@ -185,6 +115,7 @@ impl ImportMap {
185 is_type_in_ns: bool, 115 is_type_in_ns: bool,
186 original_import_info: &ImportInfo, 116 original_import_info: &ImportInfo,
187 ) { 117 ) {
118 let _p = profile::span("collect_trait_assoc_items");
188 for (assoc_item_name, item) in &db.trait_data(tr).items { 119 for (assoc_item_name, item) in &db.trait_data(tr).items {
189 let module_def_id = match item { 120 let module_def_id = match item {
190 AssocItemId::FunctionId(f) => ModuleDefId::from(*f), 121 AssocItemId::FunctionId(f) => ModuleDefId::from(*f),
@@ -210,6 +141,84 @@ impl ImportMap {
210 } 141 }
211} 142}
212 143
144fn collect_import_map(db: &dyn DefDatabase, krate: CrateId) -> ImportMap {
145 let _p = profile::span("collect_import_map");
146
147 let def_map = db.crate_def_map(krate);
148 let mut import_map = ImportMap::default();
149
150 // We look only into modules that are public(ly reexported), starting with the crate root.
151 let empty = ImportPath { segments: vec![] };
152 let root = def_map.module_id(def_map.root());
153 let mut worklist = vec![(root, empty)];
154 while let Some((module, mod_path)) = worklist.pop() {
155 let ext_def_map;
156 let mod_data = if module.krate == krate {
157 &def_map[module.local_id]
158 } else {
159 // The crate might reexport a module defined in another crate.
160 ext_def_map = module.def_map(db);
161 &ext_def_map[module.local_id]
162 };
163
164 let visible_items = mod_data.scope.entries().filter_map(|(name, per_ns)| {
165 let per_ns = per_ns.filter_visibility(|vis| vis == Visibility::Public);
166 if per_ns.is_none() {
167 None
168 } else {
169 Some((name, per_ns))
170 }
171 });
172
173 for (name, per_ns) in visible_items {
174 let mk_path = || {
175 let mut path = mod_path.clone();
176 path.segments.push(name.clone());
177 path
178 };
179
180 for item in per_ns.iter_items() {
181 let path = mk_path();
182 let path_len = path.len();
183 let import_info =
184 ImportInfo { path, container: module, is_trait_assoc_item: false };
185
186 if let Some(ModuleDefId::TraitId(tr)) = item.as_module_def_id() {
187 import_map.collect_trait_assoc_items(
188 db,
189 tr,
190 matches!(item, ItemInNs::Types(_)),
191 &import_info,
192 );
193 }
194
195 match import_map.map.entry(item) {
196 Entry::Vacant(entry) => {
197 entry.insert(import_info);
198 }
199 Entry::Occupied(mut entry) => {
200 // If the new path is shorter, prefer that one.
201 if path_len < entry.get().path.len() {
202 *entry.get_mut() = import_info;
203 } else {
204 continue;
205 }
206 }
207 }
208
209 // If we've just added a path to a module, descend into it. We might traverse
210 // modules multiple times, but only if the new path to it is shorter than the
211 // first (else we `continue` above).
212 if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
213 worklist.push((mod_id, mk_path()));
214 }
215 }
216 }
217 }
218
219 import_map
220}
221
213impl PartialEq for ImportMap { 222impl PartialEq for ImportMap {
214 fn eq(&self, other: &Self) -> bool { 223 fn eq(&self, other: &Self) -> bool {
215 // `fst` and `importables` are built from `map`, so we don't need to compare them. 224 // `fst` and `importables` are built from `map`, so we don't need to compare them.
@@ -240,17 +249,12 @@ impl fmt::Debug for ImportMap {
240} 249}
241 250
242fn fst_path(path: &ImportPath) -> String { 251fn fst_path(path: &ImportPath) -> String {
252 let _p = profile::span("fst_path");
243 let mut s = path.to_string(); 253 let mut s = path.to_string();
244 s.make_ascii_lowercase(); 254 s.make_ascii_lowercase();
245 s 255 s
246} 256}
247 257
248fn cmp((_, lhs): &(&ItemInNs, &ImportInfo), (_, rhs): &(&ItemInNs, &ImportInfo)) -> Ordering {
249 let lhs_str = fst_path(&lhs.path);
250 let rhs_str = fst_path(&rhs.path);
251 lhs_str.cmp(&rhs_str)
252}
253
254#[derive(Debug, Eq, PartialEq, Hash)] 258#[derive(Debug, Eq, PartialEq, Hash)]
255pub enum ImportKind { 259pub enum ImportKind {
256 Module, 260 Module,
@@ -338,6 +342,7 @@ impl Query {
338 } 342 }
339 343
340 fn import_matches(&self, import: &ImportInfo, enforce_lowercase: bool) -> bool { 344 fn import_matches(&self, import: &ImportInfo, enforce_lowercase: bool) -> bool {
345 let _p = profile::span("import_map::Query::import_matches");
341 if import.is_trait_assoc_item { 346 if import.is_trait_assoc_item {
342 if self.exclude_import_kinds.contains(&ImportKind::AssociatedItem) { 347 if self.exclude_import_kinds.contains(&ImportKind::AssociatedItem) {
343 return false; 348 return false;