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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
use crate::stable_hasher::{HashStable, StableHasher};
use std::cmp::Ordering;
use std::hash::{Hash, Hasher};
use std::ops::Deref;
use std::ptr;
use crate::fingerprint::Fingerprint;
mod private {
#[derive(Clone, Copy, Debug)]
pub struct PrivateZst;
}
/// A reference to a value that is interned, and is known to be unique.
///
/// Note that it is possible to have a `T` and a `Interned<T>` that are (or
/// refer to) equal but different values. But if you have two different
/// `Interned<T>`s, they both refer to the same value, at a single location in
/// memory. This means that equality and hashing can be done on the value's
/// address rather than the value's contents, which can improve performance.
///
/// The `PrivateZst` field means you can pattern match with `Interned(v, _)`
/// but you can only construct a `Interned` with `new_unchecked`, and not
/// directly.
#[derive(Debug)]
#[rustc_pass_by_value]
pub struct Interned<'a, T>(pub &'a T, pub private::PrivateZst);
impl<'a, T> Interned<'a, T> {
/// Create a new `Interned` value. The value referred to *must* be interned
/// and thus be unique, and it *must* remain unique in the future. This
/// function has `_unchecked` in the name but is not `unsafe`, because if
/// the uniqueness condition is violated condition it will cause incorrect
/// behaviour but will not affect memory safety.
#[inline]
pub const fn new_unchecked(t: &'a T) -> Self {
Interned(t, private::PrivateZst)
}
}
impl<'a, T> Clone for Interned<'a, T> {
fn clone(&self) -> Self {
*self
}
}
impl<'a, T> Copy for Interned<'a, T> {}
impl<'a, T> Deref for Interned<'a, T> {
type Target = T;
#[inline]
fn deref(&self) -> &T {
self.0
}
}
impl<'a, T> PartialEq for Interned<'a, T> {
#[inline]
fn eq(&self, other: &Self) -> bool {
// Pointer equality implies equality, due to the uniqueness constraint.
ptr::eq(self.0, other.0)
}
}
impl<'a, T> Eq for Interned<'a, T> {}
impl<'a, T: PartialOrd> PartialOrd for Interned<'a, T> {
fn partial_cmp(&self, other: &Interned<'a, T>) -> Option<Ordering> {
// Pointer equality implies equality, due to the uniqueness constraint,
// but the contents must be compared otherwise.
if ptr::eq(self.0, other.0) {
Some(Ordering::Equal)
} else {
let res = self.0.partial_cmp(&other.0);
debug_assert_ne!(res, Some(Ordering::Equal));
res
}
}
}
impl<'a, T: Ord> Ord for Interned<'a, T> {
fn cmp(&self, other: &Interned<'a, T>) -> Ordering {
// Pointer equality implies equality, due to the uniqueness constraint,
// but the contents must be compared otherwise.
if ptr::eq(self.0, other.0) {
Ordering::Equal
} else {
let res = self.0.cmp(&other.0);
debug_assert_ne!(res, Ordering::Equal);
res
}
}
}
impl<'a, T> Hash for Interned<'a, T> {
#[inline]
fn hash<H: Hasher>(&self, s: &mut H) {
// Pointer hashing is sufficient, due to the uniqueness constraint.
ptr::hash(self.0, s)
}
}
impl<T, CTX> HashStable<CTX> for Interned<'_, T>
where
T: HashStable<CTX>,
{
fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
self.0.hash_stable(hcx, hasher);
}
}
/// A helper trait so that `Interned` things can cache stable hashes reproducibly.
pub trait InternedHashingContext {
fn with_def_path_and_no_spans(&mut self, f: impl FnOnce(&mut Self));
}
/// A helper type that you can wrap round your own type in order to automatically
/// cache the stable hash on creation and not recompute it whenever the stable hash
/// of the type is computed.
/// This is only done in incremental mode. You can also opt out of caching by using
/// StableHash::ZERO for the hash, in which case the hash gets computed each time.
/// This is useful if you have values that you intern but never (can?) use for stable
/// hashing.
#[derive(Copy, Clone)]
pub struct WithStableHash<T> {
pub internee: T,
pub stable_hash: Fingerprint,
}
impl<T: PartialEq> PartialEq for WithStableHash<T> {
#[inline]
fn eq(&self, other: &Self) -> bool {
self.internee.eq(&other.internee)
}
}
impl<T: Eq> Eq for WithStableHash<T> {}
impl<T: Ord> PartialOrd for WithStableHash<T> {
fn partial_cmp(&self, other: &WithStableHash<T>) -> Option<Ordering> {
Some(self.internee.cmp(&other.internee))
}
}
impl<T: Ord> Ord for WithStableHash<T> {
fn cmp(&self, other: &WithStableHash<T>) -> Ordering {
self.internee.cmp(&other.internee)
}
}
impl<T> Deref for WithStableHash<T> {
type Target = T;
#[inline]
fn deref(&self) -> &T {
&self.internee
}
}
impl<T: Hash> Hash for WithStableHash<T> {
#[inline]
fn hash<H: Hasher>(&self, s: &mut H) {
self.internee.hash(s)
}
}
impl<T: HashStable<CTX>, CTX: InternedHashingContext> HashStable<CTX> for WithStableHash<T> {
fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
if self.stable_hash == Fingerprint::ZERO || cfg!(debug_assertions) {
// No cached hash available. This can only mean that incremental is disabled.
// We don't cache stable hashes in non-incremental mode, because they are used
// so rarely that the performance actually suffers.
// We need to build the hash as if we cached it and then hash that hash, as
// otherwise the hashes will differ between cached and non-cached mode.
let stable_hash: Fingerprint = {
let mut hasher = StableHasher::new();
hcx.with_def_path_and_no_spans(|hcx| self.internee.hash_stable(hcx, &mut hasher));
hasher.finish()
};
if cfg!(debug_assertions) && self.stable_hash != Fingerprint::ZERO {
assert_eq!(
stable_hash, self.stable_hash,
"cached stable hash does not match freshly computed stable hash"
);
}
stable_hash.hash_stable(hcx, hasher);
} else {
self.stable_hash.hash_stable(hcx, hasher);
}
}
}
#[cfg(test)]
mod tests;
|
