refquiem 0.1.0

A cargo requiem for the refs your Rust code left behind
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

//! Interned identifiers and item paths shared by every snapshot of a scan.

use std::collections::HashMap;
use std::hash::{BuildHasher, RandomState};

use hashbrown::HashTable;

use crate::ItemKind;

/// An interned identifier.
pub(crate) type Sym = u32;

/// An interned item path.
pub(crate) type PathId = u32;

/// Identifiers and paths, each stored once.
#[derive(Default)]
pub(crate) struct Interner {
    syms: HashMap<Box<str>, Sym>,
    names: Vec<Box<str>>,
    /// The segments of every path, one path after another.
    arena: Vec<Sym>,
    /// Where the segments of each path end in `arena`.
    ends: Vec<u32>,
    /// Every path, found by the hash of its segments.
    paths: HashTable<PathId>,
    state: RandomState,
    kinds: Vec<ItemKind>,
    /// Paths [`Self::child`] found, by their parent and last segment.
    children: HashMap<(PathId, Sym), PathId>,
    /// The segments [`Self::child`] builds a path in.
    scratch: Vec<Sym>,
}

impl Interner {
    /// The symbol of `name`, interning it when new.
    pub(crate) fn sym(&mut self, name: &str) -> Sym {
        if let Some(&sym) = self.syms.get(name) {
            return sym;
        }
        let sym = Sym::try_from(self.names.len()).expect("fewer than 2^32 identifiers");
        self.names.push(name.into());
        self.syms.insert(name.into(), sym);
        sym
    }

    /// The symbol of `name` when it was ever interned.
    pub(crate) fn find_sym(&self, name: &str) -> Option<Sym> {
        self.syms.get(name).copied()
    }

    /// The identifier behind `sym`.
    pub(crate) fn name(&self, sym: Sym) -> &str {
        &self.names[index(sym)]
    }

    /// The id of `segments`, interning it with `kind` when new. The first kind seen sticks.
    pub(crate) fn path(&mut self, segments: &[Sym], kind: ItemKind) -> PathId {
        let hash = self.state.hash_one(segments);
        let known = self.paths.find(hash, |&known| {
            span(&self.arena, &self.ends, known) == segments
        });
        if let Some(&id) = known {
            return id;
        }
        let id = PathId::try_from(self.ends.len()).expect("fewer than 2^32 paths");
        self.arena.extend_from_slice(segments);
        let end = u32::try_from(self.arena.len()).expect("fewer than 2^32 segments");
        self.ends.push(end);
        let Self {
            arena,
            ends,
            paths,
            state,
            ..
        } = self;
        paths.insert_unique(hash, id, |&known| state.hash_one(span(arena, ends, known)));
        self.kinds.push(kind);
        id
    }

    /// The id of `segments` when it was ever interned.
    pub(crate) fn find_path(&self, segments: &[Sym]) -> Option<PathId> {
        let hash = self.state.hash_one(segments);
        self.paths
            .find(hash, |&known| {
                span(&self.arena, &self.ends, known) == segments
            })
            .copied()
    }

    /// The id of `parent`'s segments followed by `last`, interning it with `kind` when new as
    /// [`Self::path`] does, without hashing the whole segment list again for a pair seen before.
    pub(crate) fn child(&mut self, parent: PathId, last: Sym, kind: ItemKind) -> PathId {
        if let Some(&id) = self.children.get(&(parent, last)) {
            return id;
        }
        let mut path = std::mem::take(&mut self.scratch);
        path.clear();
        path.extend_from_slice(self.segments(parent));
        path.push(last);
        let id = self.path(&path, kind);
        self.scratch = path;
        self.children.insert((parent, last), id);
        id
    }

    /// The segments of `id`.
    pub(crate) fn segments(&self, id: PathId) -> &[Sym] {
        span(&self.arena, &self.ends, id)
    }

    /// The kind `id` was first seen with.
    pub(crate) fn kind(&self, id: PathId) -> ItemKind {
        self.kinds[index(id)]
    }

    /// `id` spelled with `::` separators.
    pub(crate) fn display(&self, id: PathId) -> String {
        self.join(self.segments(id))
    }

    /// `segments` spelled with `::` separators.
    pub(crate) fn join(&self, segments: &[Sym]) -> String {
        let mut out = String::new();
        for (i, &sym) in segments.iter().enumerate() {
            if i > 0 {
                out.push_str("::");
            }
            out.push_str(self.name(sym));
        }
        out
    }
}

fn index(id: u32) -> usize {
    usize::try_from(id).expect("u32 ids fit in usize on supported targets")
}

/// The segments of path `id` in `arena`, whose paths end at `ends`.
fn span<'a>(arena: &'a [Sym], ends: &[u32], id: PathId) -> &'a [Sym] {
    let id = index(id);
    let start = id.checked_sub(1).map_or(0, |before| index(ends[before]));
    &arena[start..index(ends[id])]
}