rls_analysis/
analysis.rs

1use fst;
2use std::collections::{BTreeMap, HashMap, HashSet};
3use std::iter;
4use std::path::{Path, PathBuf};
5use std::time::SystemTime;
6
7use crate::raw::{CrateId, DefKind};
8use crate::{Id, Span, SymbolQuery};
9use span::{Column, Row, ZeroIndexed};
10
11/// This is the main database that contains all the collected symbol information,
12/// such as definitions, their mapping between spans, hierarchy and so on,
13/// organized in a per-crate fashion.
14pub(crate) struct Analysis {
15    /// Contains lowered data with global inter-crate `Id`s per each crate.
16    pub per_crate: HashMap<CrateId, PerCrateAnalysis>,
17
18    // This is a bit of a hack and should be considered temporary. A def has an
19    // entry if there exists an import of the def which aliases it. We use this
20    // for find_all_refs with unique spans to ensure that clients don't rename a
21    // definition when they only mean to rename an alias.
22    //
23    // In the future we should handle imports, in particular aliasing ones, more
24    // explicitly and then this can be removed.
25    pub(crate) aliased_imports: HashSet<Id>,
26
27    // Maps a crate names to the crate ids for all crates with that name.
28    pub(crate) crate_names: HashMap<String, Vec<CrateId>>,
29
30    pub doc_url_base: String,
31    pub src_url_base: String,
32}
33
34pub struct PerCrateAnalysis {
35    // Map span to id of def (either because it is the span of the def, or of
36    // the def for the ref).
37    pub def_id_for_span: HashMap<Span, Ref>,
38    pub defs: HashMap<Id, Def>,
39    pub defs_per_file: HashMap<PathBuf, Vec<Id>>,
40    pub children: HashMap<Id, HashSet<Id>>,
41    pub def_names: HashMap<String, Vec<Id>>,
42
43    // Index of all symbols that powers the search.
44    // See `SymbolQuery`.
45    pub def_fst: fst::Map<Vec<u8>>,
46    pub def_fst_values: Vec<Vec<Id>>,
47
48    pub ref_spans: HashMap<Id, Vec<Span>>,
49    pub globs: HashMap<Span, Glob>,
50    pub impls: HashMap<Id, Vec<Span>>,
51    pub idents: HashMap<PathBuf, IdentsByLine>,
52
53    pub root_id: Option<Id>,
54    pub timestamp: SystemTime,
55    pub path: Option<PathBuf>,
56    // All definitions in this crate will include the global_crate_num. See
57    // lowering::id_from_compiler_id for details of how.
58    // global_crate_num is not available until after lowering.
59    pub global_crate_num: u32,
60}
61
62#[derive(Debug, Clone)]
63pub enum Ref {
64    // The common case - a reference to a single definition.
65    Id(Id),
66    // Two defs contribute to a single reference, occurs in the field name
67    // shorthand, maybe other places.
68    Double(Id, Id),
69    // Multiple ids, we record only the first def we found, plus a count of defs.
70    // Should only happen due to generated code which has not been well-filtered
71    // by the compiler.
72    Multi(Id, usize),
73}
74
75impl Ref {
76    pub fn some_id(&self) -> Id {
77        match *self {
78            Ref::Id(id) => id,
79            Ref::Double(id, _) => id,
80            Ref::Multi(id, _) => id,
81        }
82    }
83
84    pub fn add_id(&self, def_id: Id) -> Ref {
85        match *self {
86            Ref::Id(id) => Ref::Double(id, def_id),
87            Ref::Double(id, _) => Ref::Multi(id, 3),
88            Ref::Multi(id, n) => Ref::Multi(id, n + 1),
89        }
90    }
91}
92
93#[derive(Debug, Clone)]
94pub struct Def {
95    pub kind: DefKind,
96    pub span: Span,
97    pub name: String,
98    pub qualname: String,
99    pub distro_crate: bool,
100    pub parent: Option<Id>,
101    pub value: String,
102    pub docs: String,
103    // pub sig: Option<Signature>,
104}
105
106pub type IdentsByLine = BTreeMap<Row<ZeroIndexed>, IdentsByColumn>;
107pub type IdentsByColumn = BTreeMap<Column<ZeroIndexed>, IdentBound>;
108
109/// We store the identifiers for a file in a BTreeMap ordered by starting index.
110/// This struct contains the rest of the information we need to create an `Ident`.
111///
112/// We're optimising for space, rather than speed (of getting an Ident), because
113/// we have to build the whole index for every file (which is a lot for a large
114/// project), whereas we only get idents a few at a time and not very often.
115#[derive(new, Clone, Debug)]
116pub struct IdentBound {
117    pub column_end: Column<ZeroIndexed>,
118    pub id: Id,
119    pub kind: IdentKind,
120}
121
122#[derive(Copy, Clone, Debug, Eq, PartialEq)]
123pub enum IdentKind {
124    Def,
125    Ref,
126}
127
128/// An identifier (either a reference or definition).
129///
130/// This struct represents the syntactic name, use the `id` to look up semantic
131/// information.
132#[derive(new, Clone, Debug)]
133pub struct Ident {
134    pub span: Span,
135    pub id: Id,
136    pub kind: IdentKind,
137}
138
139#[derive(Debug, Clone)]
140pub struct Signature {
141    pub span: Span,
142    pub text: String,
143    pub ident_start: u32,
144    pub ident_end: u32,
145    pub defs: Vec<SigElement>,
146    pub refs: Vec<SigElement>,
147}
148
149#[derive(Debug, Clone)]
150pub struct SigElement {
151    pub id: Id,
152    pub start: usize,
153    pub end: usize,
154}
155
156#[derive(Debug)]
157pub struct Glob {
158    pub value: String,
159}
160
161impl PerCrateAnalysis {
162    pub fn new(timestamp: SystemTime, path: Option<PathBuf>) -> PerCrateAnalysis {
163        let empty_fst = fst::Map::from_iter(iter::empty::<(String, u64)>()).unwrap();
164        PerCrateAnalysis {
165            def_id_for_span: HashMap::new(),
166            defs: HashMap::new(),
167            defs_per_file: HashMap::new(),
168            children: HashMap::new(),
169            def_names: HashMap::new(),
170            def_fst: empty_fst,
171            def_fst_values: Vec::new(),
172            ref_spans: HashMap::new(),
173            globs: HashMap::new(),
174            impls: HashMap::new(),
175            idents: HashMap::new(),
176            root_id: None,
177            timestamp,
178            path,
179            global_crate_num: 0,
180        }
181    }
182
183    // Returns true if there is a def in this crate with the same crate-local id
184    // and span as `def`.
185    pub(crate) fn has_congruent_def(&self, local_id: u32, span: &Span) -> bool {
186        let id = Id::from_crate_and_local(self.global_crate_num, local_id);
187        match self.defs.get(&id) {
188            Some(existing) => span == &existing.span,
189            None => false,
190        }
191    }
192
193    // Returns all identifiers which overlap with `span`. There is no guarantee about
194    // the ordering of identifiers in the result, but they will probably be roughly
195    // in order of appearance.
196    #[cfg(feature = "idents")]
197    fn idents(&self, span: &Span) -> Vec<Ident> {
198        self.idents
199            .get(&span.file)
200            .map(|by_line| {
201                (span.range.row_start..=span.range.row_end)
202                    .flat_map(|line| {
203                        let vec = by_line
204                            .get(&line)
205                            .iter()
206                            .flat_map(|by_col| {
207                                by_col.into_iter().filter_map(|(col_start, id)| {
208                                    if col_start <= &span.range.col_end
209                                        && id.column_end >= span.range.col_start
210                                    {
211                                        Some(Ident::new(
212                                            Span::new(
213                                                line,
214                                                line,
215                                                *col_start,
216                                                id.column_end,
217                                                span.file.clone(),
218                                            ),
219                                            id.id,
220                                            id.kind,
221                                        ))
222                                    } else {
223                                        None
224                                    }
225                                })
226                            })
227                            .collect::<Vec<Ident>>();
228                        vec.into_iter()
229                    })
230                    .collect::<Vec<Ident>>()
231            })
232            .unwrap_or_else(Vec::new)
233    }
234}
235
236impl Analysis {
237    pub fn new() -> Analysis {
238        Analysis {
239            per_crate: HashMap::new(),
240            aliased_imports: HashSet::new(),
241            crate_names: HashMap::new(),
242            // TODO don't hardcode these
243            doc_url_base: "https://doc.rust-lang.org/nightly".to_owned(),
244            src_url_base: "https://github.com/rust-lang/rust/blob/master".to_owned(),
245        }
246    }
247
248    pub fn timestamps(&self) -> HashMap<PathBuf, SystemTime> {
249        self.per_crate
250            .values()
251            .filter(|c| c.path.is_some())
252            .map(|c| (c.path.as_ref().unwrap().clone(), c.timestamp))
253            .collect()
254    }
255
256    pub fn update(&mut self, crate_id: CrateId, per_crate: PerCrateAnalysis) {
257        self.per_crate.insert(crate_id, per_crate);
258    }
259
260    pub fn has_def(&self, id: Id) -> bool {
261        self.per_crate.values().any(|c| c.defs.contains_key(&id))
262    }
263
264    pub fn for_each_crate<F, T>(&self, f: F) -> Option<T>
265    where
266        F: Fn(&PerCrateAnalysis) -> Option<T>,
267    {
268        let mut result = vec![];
269        for per_crate in self.per_crate.values() {
270            if let Some(t) = f(per_crate) {
271                result.push(t);
272            }
273        }
274
275        // This assertion is sometimes helpful for debugging, but also can cause
276        // problems where otherwise there are none.
277        // FIXME - might be worth investigating some common causes.
278        // assert!(
279        //     result.len() <= 1,
280        //     "error in for_each_crate, found {} results, expected 0 or 1",
281        //     result.len(),
282        // );
283        result.into_iter().nth(0)
284    }
285
286    pub fn for_all_crates<F, T>(&self, f: F) -> Vec<T>
287    where
288        F: Fn(&PerCrateAnalysis) -> Option<Vec<T>>,
289    {
290        let mut result = vec![];
291        for per_crate in self.per_crate.values() {
292            if let Some(this_crate) = f(per_crate) {
293                result.extend(this_crate);
294            }
295        }
296
297        result
298    }
299
300    pub fn def_id_for_span(&self, span: &Span) -> Option<Id> {
301        self.ref_for_span(span).map(|r| r.some_id())
302    }
303
304    pub fn ref_for_span(&self, span: &Span) -> Option<Ref> {
305        self.for_each_crate(|c| c.def_id_for_span.get(span).cloned())
306    }
307
308    // Like def_id_for_span, but will only return a def_id if it is in the same
309    // crate.
310    pub fn local_def_id_for_span(&self, span: &Span) -> Option<Id> {
311        self.for_each_crate(|c| {
312            c.def_id_for_span.get(span).map(Ref::some_id).and_then(|id| {
313                if c.defs.contains_key(&id) {
314                    Some(id)
315                } else {
316                    None
317                }
318            })
319        })
320    }
321
322    pub fn with_defs<F, T>(&self, id: Id, f: F) -> Option<T>
323    where
324        F: Fn(&Def) -> T,
325    {
326        self.for_each_crate(|c| c.defs.get(&id).map(&f))
327    }
328
329    pub fn with_defs_and_then<F, T>(&self, id: Id, f: F) -> Option<T>
330    where
331        F: Fn(&Def) -> Option<T>,
332    {
333        self.for_each_crate(|c| c.defs.get(&id).and_then(&f))
334    }
335
336    pub fn with_globs<F, T>(&self, span: &Span, f: F) -> Option<T>
337    where
338        F: Fn(&Glob) -> T,
339    {
340        self.for_each_crate(|c| c.globs.get(span).map(&f))
341    }
342
343    pub fn for_each_child<F, T>(&self, id: Id, mut f: F) -> Option<Vec<T>>
344    where
345        F: FnMut(Id, &Def) -> T,
346    {
347        for per_crate in self.per_crate.values() {
348            if let Some(children) = per_crate.children.get(&id) {
349                return Some(
350                    children
351                        .iter()
352                        .filter_map(|id| {
353                            let def = per_crate.defs.get(id);
354                            if def.is_none() {
355                                info!("def not found for {}", id);
356                            }
357                            def.map(|def| f(*id, def))
358                        })
359                        .collect(),
360                );
361            }
362        }
363
364        Some(vec![])
365    }
366
367    pub fn with_ref_spans<F, T>(&self, id: Id, f: F) -> Option<T>
368    where
369        F: Fn(&Vec<Span>) -> Option<T>,
370    {
371        self.for_each_crate(|c| c.ref_spans.get(&id).and_then(&f))
372    }
373
374    pub fn with_defs_per_file<F, T>(&self, file: &Path, f: F) -> Option<T>
375    where
376        F: Fn(&Vec<Id>) -> T,
377    {
378        self.for_each_crate(|c| c.defs_per_file.get(file).map(&f))
379    }
380
381    #[cfg(feature = "idents")]
382    pub fn idents(&self, span: &Span) -> Vec<Ident> {
383        self.for_each_crate(|c| {
384            let result = c.idents(span);
385            if result.is_empty() {
386                None
387            } else {
388                Some(result)
389            }
390        })
391        .unwrap_or_else(Vec::new)
392    }
393
394    pub fn query_defs(&self, query: SymbolQuery) -> Vec<Def> {
395        let mut crates = Vec::with_capacity(self.per_crate.len());
396        let stream = query.build_stream(self.per_crate.values().map(|c| {
397            crates.push(c);
398            &c.def_fst
399        }));
400
401        query.search_stream(stream, |acc, e| {
402            let c = &crates[e.index];
403            let ids = &c.def_fst_values[e.value as usize];
404            acc.extend(ids.iter().flat_map(|id| c.defs.get(id)).cloned());
405        })
406    }
407
408    pub fn with_def_names<F, T>(&self, name: &str, f: F) -> Vec<T>
409    where
410        F: Fn(&Vec<Id>) -> Vec<T>,
411    {
412        self.for_all_crates(|c| c.def_names.get(name).map(&f))
413    }
414}
rls_analysis/analysis.rs

rls_analysis/
analysis.rs
