1use std::hash::{BuildHasher, Hash, Hasher};
2use std::marker::PhantomData;
3use std::mem;
4use std::num::NonZero;
5
6use rustc_index::bit_set::{self, DenseBitSet};
7use rustc_index::{Idx, IndexSlice, IndexVec};
8use smallvec::SmallVec;
9
10#[cfg(test)]
11mod tests;
12
13use rustc_hashes::{Hash64, Hash128};
14pub use rustc_stable_hash::{
15 FromStableHash, SipHasher128Hash as StableHasherHash, StableSipHasher128 as StableHasher,
16};
17
18pub trait HashStable<CTX> {
45 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher);
46}
47
48pub trait ToStableHashKey<HCX> {
52 type KeyType: Ord + Sized + HashStable<HCX>;
53 fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
54}
55
56pub trait StableOrd: Ord {
86 const CAN_USE_UNSTABLE_SORT: bool;
87
88 const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: ();
91}
92
93impl<T: StableOrd> StableOrd for &T {
94 const CAN_USE_UNSTABLE_SORT: bool = T::CAN_USE_UNSTABLE_SORT;
95
96 const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: () = ();
100}
101
102pub trait StableCompare {
113 const CAN_USE_UNSTABLE_SORT: bool;
114
115 fn stable_cmp(&self, other: &Self) -> std::cmp::Ordering;
116}
117
118impl<T: StableOrd> StableCompare for T {
121 const CAN_USE_UNSTABLE_SORT: bool = T::CAN_USE_UNSTABLE_SORT;
122
123 fn stable_cmp(&self, other: &Self) -> std::cmp::Ordering {
124 self.cmp(other)
125 }
126}
127
128macro_rules! impl_stable_traits_for_trivial_type {
138 ($t:ty) => {
139 impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t {
140 #[inline]
141 fn hash_stable(&self, _: &mut CTX, hasher: &mut $crate::stable_hasher::StableHasher) {
142 ::std::hash::Hash::hash(self, hasher);
143 }
144 }
145
146 impl $crate::stable_hasher::StableOrd for $t {
147 const CAN_USE_UNSTABLE_SORT: bool = true;
148
149 const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: () = ();
152 }
153 };
154}
155
156pub(crate) use impl_stable_traits_for_trivial_type;
157
158impl_stable_traits_for_trivial_type!(i8);
159impl_stable_traits_for_trivial_type!(i16);
160impl_stable_traits_for_trivial_type!(i32);
161impl_stable_traits_for_trivial_type!(i64);
162impl_stable_traits_for_trivial_type!(isize);
163
164impl_stable_traits_for_trivial_type!(u8);
165impl_stable_traits_for_trivial_type!(u16);
166impl_stable_traits_for_trivial_type!(u32);
167impl_stable_traits_for_trivial_type!(u64);
168impl_stable_traits_for_trivial_type!(usize);
169
170impl_stable_traits_for_trivial_type!(u128);
171impl_stable_traits_for_trivial_type!(i128);
172
173impl_stable_traits_for_trivial_type!(char);
174impl_stable_traits_for_trivial_type!(());
175
176impl_stable_traits_for_trivial_type!(Hash64);
177
178impl<CTX> HashStable<CTX> for Hash128 {
181 #[inline]
182 fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
183 self.as_u128().hash(hasher);
184 }
185}
186
187impl StableOrd for Hash128 {
188 const CAN_USE_UNSTABLE_SORT: bool = true;
189
190 const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: () = ();
193}
194
195impl<CTX> HashStable<CTX> for ! {
196 fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) {
197 unreachable!()
198 }
199}
200
201impl<CTX, T> HashStable<CTX> for PhantomData<T> {
202 fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) {}
203}
204
205impl<CTX> HashStable<CTX> for NonZero<u32> {
206 #[inline]
207 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
208 self.get().hash_stable(ctx, hasher)
209 }
210}
211
212impl<CTX> HashStable<CTX> for NonZero<usize> {
213 #[inline]
214 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
215 self.get().hash_stable(ctx, hasher)
216 }
217}
218
219impl<CTX> HashStable<CTX> for f32 {
220 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
221 let val: u32 = self.to_bits();
222 val.hash_stable(ctx, hasher);
223 }
224}
225
226impl<CTX> HashStable<CTX> for f64 {
227 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
228 let val: u64 = self.to_bits();
229 val.hash_stable(ctx, hasher);
230 }
231}
232
233impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
234 #[inline]
235 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
236 (*self as i8).hash_stable(ctx, hasher);
237 }
238}
239
240impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
241 #[inline]
242 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
243 let (ref _0,) = *self;
244 _0.hash_stable(ctx, hasher);
245 }
246}
247
248impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
249 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
250 let (ref _0, ref _1) = *self;
251 _0.hash_stable(ctx, hasher);
252 _1.hash_stable(ctx, hasher);
253 }
254}
255
256impl<T1: StableOrd, T2: StableOrd> StableOrd for (T1, T2) {
257 const CAN_USE_UNSTABLE_SORT: bool = T1::CAN_USE_UNSTABLE_SORT && T2::CAN_USE_UNSTABLE_SORT;
258
259 const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: () = ();
262}
263
264impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
265where
266 T1: HashStable<CTX>,
267 T2: HashStable<CTX>,
268 T3: HashStable<CTX>,
269{
270 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
271 let (ref _0, ref _1, ref _2) = *self;
272 _0.hash_stable(ctx, hasher);
273 _1.hash_stable(ctx, hasher);
274 _2.hash_stable(ctx, hasher);
275 }
276}
277
278impl<T1: StableOrd, T2: StableOrd, T3: StableOrd> StableOrd for (T1, T2, T3) {
279 const CAN_USE_UNSTABLE_SORT: bool =
280 T1::CAN_USE_UNSTABLE_SORT && T2::CAN_USE_UNSTABLE_SORT && T3::CAN_USE_UNSTABLE_SORT;
281
282 const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: () = ();
285}
286
287impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
288where
289 T1: HashStable<CTX>,
290 T2: HashStable<CTX>,
291 T3: HashStable<CTX>,
292 T4: HashStable<CTX>,
293{
294 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
295 let (ref _0, ref _1, ref _2, ref _3) = *self;
296 _0.hash_stable(ctx, hasher);
297 _1.hash_stable(ctx, hasher);
298 _2.hash_stable(ctx, hasher);
299 _3.hash_stable(ctx, hasher);
300 }
301}
302
303impl<T1: StableOrd, T2: StableOrd, T3: StableOrd, T4: StableOrd> StableOrd for (T1, T2, T3, T4) {
304 const CAN_USE_UNSTABLE_SORT: bool = T1::CAN_USE_UNSTABLE_SORT
305 && T2::CAN_USE_UNSTABLE_SORT
306 && T3::CAN_USE_UNSTABLE_SORT
307 && T4::CAN_USE_UNSTABLE_SORT;
308
309 const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: () = ();
312}
313
314impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
315 default fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
316 self.len().hash_stable(ctx, hasher);
317 for item in self {
318 item.hash_stable(ctx, hasher);
319 }
320 }
321}
322
323impl<CTX> HashStable<CTX> for [u8] {
324 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
325 self.len().hash_stable(ctx, hasher);
326 hasher.write(self);
327 }
328}
329
330impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
331 #[inline]
332 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
333 self[..].hash_stable(ctx, hasher);
334 }
335}
336
337impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R>
338where
339 K: HashStable<CTX> + Eq + Hash,
340 V: HashStable<CTX>,
341 R: BuildHasher,
342{
343 #[inline]
344 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
345 self.len().hash_stable(ctx, hasher);
346 for kv in self {
347 kv.hash_stable(ctx, hasher);
348 }
349 }
350}
351
352impl<K, R, CTX> HashStable<CTX> for indexmap::IndexSet<K, R>
353where
354 K: HashStable<CTX> + Eq + Hash,
355 R: BuildHasher,
356{
357 #[inline]
358 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
359 self.len().hash_stable(ctx, hasher);
360 for key in self {
361 key.hash_stable(ctx, hasher);
362 }
363 }
364}
365
366impl<A, const N: usize, CTX> HashStable<CTX> for SmallVec<[A; N]>
367where
368 A: HashStable<CTX>,
369{
370 #[inline]
371 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
372 self[..].hash_stable(ctx, hasher);
373 }
374}
375
376impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
377 #[inline]
378 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
379 (**self).hash_stable(ctx, hasher);
380 }
381}
382
383impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
384 #[inline]
385 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
386 (**self).hash_stable(ctx, hasher);
387 }
388}
389
390impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
391 #[inline]
392 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
393 (**self).hash_stable(ctx, hasher);
394 }
395}
396
397impl<CTX> HashStable<CTX> for str {
398 #[inline]
399 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
400 self.as_bytes().hash_stable(ctx, hasher);
401 }
402}
403
404impl StableOrd for &str {
405 const CAN_USE_UNSTABLE_SORT: bool = true;
406
407 const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: () = ();
410}
411
412impl<CTX> HashStable<CTX> for String {
413 #[inline]
414 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
415 self[..].hash_stable(hcx, hasher);
416 }
417}
418
419impl StableOrd for String {
420 const CAN_USE_UNSTABLE_SORT: bool = true;
421
422 const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: () = ();
425}
426
427impl<HCX> ToStableHashKey<HCX> for String {
428 type KeyType = String;
429 #[inline]
430 fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
431 self.clone()
432 }
433}
434
435impl<HCX, T1: ToStableHashKey<HCX>, T2: ToStableHashKey<HCX>> ToStableHashKey<HCX> for (T1, T2) {
436 type KeyType = (T1::KeyType, T2::KeyType);
437 #[inline]
438 fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType {
439 (self.0.to_stable_hash_key(hcx), self.1.to_stable_hash_key(hcx))
440 }
441}
442
443impl<CTX> HashStable<CTX> for bool {
444 #[inline]
445 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
446 (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
447 }
448}
449
450impl StableOrd for bool {
451 const CAN_USE_UNSTABLE_SORT: bool = true;
452
453 const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: () = ();
455}
456
457impl<T, CTX> HashStable<CTX> for Option<T>
458where
459 T: HashStable<CTX>,
460{
461 #[inline]
462 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
463 if let Some(ref value) = *self {
464 1u8.hash_stable(ctx, hasher);
465 value.hash_stable(ctx, hasher);
466 } else {
467 0u8.hash_stable(ctx, hasher);
468 }
469 }
470}
471
472impl<T: StableOrd> StableOrd for Option<T> {
473 const CAN_USE_UNSTABLE_SORT: bool = T::CAN_USE_UNSTABLE_SORT;
474
475 const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: () = ();
477}
478
479impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
480where
481 T1: HashStable<CTX>,
482 T2: HashStable<CTX>,
483{
484 #[inline]
485 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
486 mem::discriminant(self).hash_stable(ctx, hasher);
487 match *self {
488 Ok(ref x) => x.hash_stable(ctx, hasher),
489 Err(ref x) => x.hash_stable(ctx, hasher),
490 }
491 }
492}
493
494impl<'a, T, CTX> HashStable<CTX> for &'a T
495where
496 T: HashStable<CTX> + ?Sized,
497{
498 #[inline]
499 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
500 (**self).hash_stable(ctx, hasher);
501 }
502}
503
504impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
505 #[inline]
506 fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
507 ::std::hash::Hash::hash(self, hasher);
508 }
509}
510
511impl<T, CTX> HashStable<CTX> for ::std::ops::RangeInclusive<T>
512where
513 T: HashStable<CTX>,
514{
515 #[inline]
516 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
517 self.start().hash_stable(ctx, hasher);
518 self.end().hash_stable(ctx, hasher);
519 }
520}
521
522impl<I: Idx, T, CTX> HashStable<CTX> for IndexSlice<I, T>
523where
524 T: HashStable<CTX>,
525{
526 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
527 self.len().hash_stable(ctx, hasher);
528 for v in &self.raw {
529 v.hash_stable(ctx, hasher);
530 }
531 }
532}
533
534impl<I: Idx, T, CTX> HashStable<CTX> for IndexVec<I, T>
535where
536 T: HashStable<CTX>,
537{
538 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
539 self.len().hash_stable(ctx, hasher);
540 for v in &self.raw {
541 v.hash_stable(ctx, hasher);
542 }
543 }
544}
545
546impl<I: Idx, CTX> HashStable<CTX> for DenseBitSet<I> {
547 fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) {
548 ::std::hash::Hash::hash(self, hasher);
549 }
550}
551
552impl<R: Idx, C: Idx, CTX> HashStable<CTX> for bit_set::BitMatrix<R, C> {
553 fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) {
554 ::std::hash::Hash::hash(self, hasher);
555 }
556}
557
558impl<T, CTX> HashStable<CTX> for bit_set::FiniteBitSet<T>
559where
560 T: HashStable<CTX> + bit_set::FiniteBitSetTy,
561{
562 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
563 self.0.hash_stable(hcx, hasher);
564 }
565}
566
567impl_stable_traits_for_trivial_type!(::std::path::Path);
568impl_stable_traits_for_trivial_type!(::std::path::PathBuf);
569
570impl<V, HCX> !HashStable<HCX> for std::collections::HashSet<V> {}
574impl<K, V, HCX> !HashStable<HCX> for std::collections::HashMap<K, V> {}
575
576impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
577where
578 K: HashStable<HCX> + StableOrd,
579 V: HashStable<HCX>,
580{
581 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
582 self.len().hash_stable(hcx, hasher);
583 for entry in self.iter() {
584 entry.hash_stable(hcx, hasher);
585 }
586 }
587}
588
589impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
590where
591 K: HashStable<HCX> + StableOrd,
592{
593 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
594 self.len().hash_stable(hcx, hasher);
595 for entry in self.iter() {
596 entry.hash_stable(hcx, hasher);
597 }
598 }
599}
600
601#[derive(Clone, Hash, Eq, PartialEq, Debug)]
609pub struct HashingControls {
610 pub hash_spans: bool,
611}