1 use rustc_data_structures::base_n;
2 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
3 use rustc_data_structures::intern::Interned;
5 use rustc_hir::def::CtorKind;
6 use rustc_hir::def_id::{CrateNum, DefId};
7 use rustc_hir::definitions::{DefPathData, DisambiguatedDefPathData};
8 use rustc_middle::ty::layout::IntegerExt;
9 use rustc_middle::ty::print::{Print, Printer};
10 use rustc_middle::ty::subst::{GenericArg, GenericArgKind, Subst};
11 use rustc_middle::ty::{
12 self, EarlyBinder, FloatTy, Instance, IntTy, Ty, TyCtxt, TypeVisitable, UintTy,
14 use rustc_span::symbol::kw;
15 use rustc_target::abi::Integer;
16 use rustc_target::spec::abi::Abi;
22 pub(super) fn mangle<'tcx>(
24 instance: Instance<'tcx>,
25 instantiating_crate: Option<CrateNum>,
27 let def_id = instance.def_id();
28 // FIXME(eddyb) this should ideally not be needed.
29 let substs = tcx.normalize_erasing_regions(ty::ParamEnv::reveal_all(), instance.substs);
32 let mut cx = &mut SymbolMangler {
34 start_offset: prefix.len(),
35 paths: FxHashMap::default(),
36 types: FxHashMap::default(),
37 consts: FxHashMap::default(),
39 out: String::from(prefix),
42 // Append `::{shim:...#0}` to shims that can coexist with a non-shim instance.
43 let shim_kind = match instance.def {
44 ty::InstanceDef::VTableShim(_) => Some("vtable"),
45 ty::InstanceDef::ReifyShim(_) => Some("reify"),
50 cx = if let Some(shim_kind) = shim_kind {
51 cx.path_append_ns(|cx| cx.print_def_path(def_id, substs), 'S', 0, shim_kind).unwrap()
53 cx.print_def_path(def_id, substs).unwrap()
55 if let Some(instantiating_crate) = instantiating_crate {
56 cx = cx.print_def_path(instantiating_crate.as_def_id(), &[]).unwrap();
58 std::mem::take(&mut cx.out)
61 pub(super) fn mangle_typeid_for_trait_ref<'tcx>(
63 trait_ref: ty::PolyExistentialTraitRef<'tcx>,
65 // FIXME(flip1995): See comment in `mangle_typeid_for_fnabi`.
66 let mut cx = &mut SymbolMangler {
69 paths: FxHashMap::default(),
70 types: FxHashMap::default(),
71 consts: FxHashMap::default(),
75 cx = cx.print_def_path(trait_ref.def_id(), &[]).unwrap();
76 std::mem::take(&mut cx.out)
80 /// The range of distances from the root of what's
81 /// being printed, to the lifetimes in a binder.
82 /// Specifically, a `BrAnon(i)` lifetime has depth
83 /// `lifetime_depths.start + i`, going away from the
84 /// the root and towards its use site, as `i` increases.
85 /// This is used to flatten rustc's pairing of `BrAnon`
86 /// (intra-binder disambiguation) with a `DebruijnIndex`
87 /// (binder addressing), to "true" de Bruijn indices,
88 /// by subtracting the depth of a certain lifetime, from
89 /// the innermost depth at its use site.
90 lifetime_depths: Range<u32>,
93 struct SymbolMangler<'tcx> {
95 binders: Vec<BinderLevel>,
98 /// The length of the prefix in `out` (e.g. 2 for `_R`).
100 /// The values are start positions in `out`, in bytes.
101 paths: FxHashMap<(DefId, &'tcx [GenericArg<'tcx>]), usize>,
102 types: FxHashMap<Ty<'tcx>, usize>,
103 consts: FxHashMap<ty::Const<'tcx>, usize>,
106 impl<'tcx> SymbolMangler<'tcx> {
107 fn push(&mut self, s: &str) {
108 self.out.push_str(s);
111 /// Push a `_`-terminated base 62 integer, using the format
112 /// specified in the RFC as `<base-62-number>`, that is:
113 /// * `x = 0` is encoded as just the `"_"` terminator
114 /// * `x > 0` is encoded as `x - 1` in base 62, followed by `"_"`,
115 /// e.g. `1` becomes `"0_"`, `62` becomes `"Z_"`, etc.
116 fn push_integer_62(&mut self, x: u64) {
117 if let Some(x) = x.checked_sub(1) {
118 base_n::push_str(x as u128, 62, &mut self.out);
123 /// Push a `tag`-prefixed base 62 integer, when larger than `0`, that is:
124 /// * `x = 0` is encoded as `""` (nothing)
125 /// * `x > 0` is encoded as the `tag` followed by `push_integer_62(x - 1)`
126 /// e.g. `1` becomes `tag + "_"`, `2` becomes `tag + "0_"`, etc.
127 fn push_opt_integer_62(&mut self, tag: &str, x: u64) {
128 if let Some(x) = x.checked_sub(1) {
130 self.push_integer_62(x);
134 fn push_disambiguator(&mut self, dis: u64) {
135 self.push_opt_integer_62("s", dis);
138 fn push_ident(&mut self, ident: &str) {
139 let mut use_punycode = false;
140 for b in ident.bytes() {
142 b'_' | b'a'..=b'z' | b'A'..=b'Z' | b'0'..=b'9' => {}
143 0x80..=0xff => use_punycode = true,
144 _ => bug!("symbol_names: bad byte {} in ident {:?}", b, ident),
149 let ident = if use_punycode {
152 // FIXME(eddyb) we should probably roll our own punycode implementation.
153 let mut punycode_bytes = match punycode::encode(ident) {
154 Ok(s) => s.into_bytes(),
155 Err(()) => bug!("symbol_names: punycode encoding failed for ident {:?}", ident),
158 // Replace `-` with `_`.
159 if let Some(c) = punycode_bytes.iter_mut().rfind(|&&mut c| c == b'-') {
163 // FIXME(eddyb) avoid rechecking UTF-8 validity.
164 punycode_string = String::from_utf8(punycode_bytes).unwrap();
170 let _ = write!(self.out, "{}", ident.len());
172 // Write a separating `_` if necessary (leading digit or `_`).
173 if let Some('_' | '0'..='9') = ident.chars().next() {
180 fn path_append_ns<'a>(
181 mut self: &'a mut Self,
182 print_prefix: impl FnOnce(&'a mut Self) -> Result<&'a mut Self, !>,
186 ) -> Result<&'a mut Self, !> {
189 self = print_prefix(self)?;
190 self.push_disambiguator(disambiguator as u64);
191 self.push_ident(name);
195 fn print_backref(&mut self, i: usize) -> Result<&mut Self, !> {
197 self.push_integer_62((i - self.start_offset) as u64);
202 mut self: &'a mut Self,
203 value: &ty::Binder<'tcx, T>,
204 print_value: impl FnOnce(&'a mut Self, &T) -> Result<&'a mut Self, !>,
205 ) -> Result<&'a mut Self, !>
207 T: TypeVisitable<'tcx>,
209 let regions = if value.has_late_bound_regions() {
210 self.tcx.collect_referenced_late_bound_regions(value)
215 let mut lifetime_depths =
216 self.binders.last().map(|b| b.lifetime_depths.end).map_or(0..0, |i| i..i);
218 let lifetimes = regions
222 _ => bug!("symbol_names: non-anonymized region `{:?}` in `{:?}`", br, value),
225 .map_or(0, |max| max + 1);
227 self.push_opt_integer_62("G", lifetimes as u64);
228 lifetime_depths.end += lifetimes;
230 self.binders.push(BinderLevel { lifetime_depths });
231 self = print_value(self, value.as_ref().skip_binder())?;
238 impl<'tcx> Printer<'tcx> for &mut SymbolMangler<'tcx> {
244 type DynExistential = Self;
247 fn tcx(&self) -> TyCtxt<'tcx> {
254 substs: &'tcx [GenericArg<'tcx>],
255 ) -> Result<Self::Path, Self::Error> {
256 if let Some(&i) = self.paths.get(&(def_id, substs)) {
257 return self.print_backref(i);
259 let start = self.out.len();
261 self = self.default_print_def_path(def_id, substs)?;
263 // Only cache paths that do not refer to an enclosing
264 // binder (which would change depending on context).
265 if !substs.iter().any(|k| k.has_escaping_bound_vars()) {
266 self.paths.insert((def_id, substs), start);
274 substs: &'tcx [GenericArg<'tcx>],
275 mut self_ty: Ty<'tcx>,
276 mut impl_trait_ref: Option<ty::TraitRef<'tcx>>,
277 ) -> Result<Self::Path, Self::Error> {
278 let key = self.tcx.def_key(impl_def_id);
279 let parent_def_id = DefId { index: key.parent.unwrap(), ..impl_def_id };
281 let mut param_env = self.tcx.param_env_reveal_all_normalized(impl_def_id);
282 if !substs.is_empty() {
283 param_env = EarlyBinder(param_env).subst(self.tcx, substs);
286 match &mut impl_trait_ref {
287 Some(impl_trait_ref) => {
288 assert_eq!(impl_trait_ref.self_ty(), self_ty);
289 *impl_trait_ref = self.tcx.normalize_erasing_regions(param_env, *impl_trait_ref);
290 self_ty = impl_trait_ref.self_ty();
293 self_ty = self.tcx.normalize_erasing_regions(param_env, self_ty);
297 self.push(match impl_trait_ref {
302 // Encode impl generic params if the substitutions contain parameters (implying
303 // polymorphization is enabled) and this isn't an inherent impl.
304 if impl_trait_ref.is_some() && substs.iter().any(|a| a.has_param_types_or_consts()) {
305 self = self.path_generic_args(
308 |cx| cx.print_def_path(parent_def_id, &[]),
310 key.disambiguated_data.disambiguator as u64,
317 self.push_disambiguator(key.disambiguated_data.disambiguator as u64);
318 self = self.print_def_path(parent_def_id, &[])?;
321 self = self_ty.print(self)?;
323 if let Some(trait_ref) = impl_trait_ref {
324 self = self.print_def_path(trait_ref.def_id, trait_ref.substs)?;
330 fn print_region(self, region: ty::Region<'_>) -> Result<Self::Region, Self::Error> {
331 let i = match *region {
332 // Erased lifetimes use the index 0, for a
333 // shorter mangling of `L_`.
336 // Late-bound lifetimes use indices starting at 1,
337 // see `BinderLevel` for more details.
338 ty::ReLateBound(debruijn, ty::BoundRegion { kind: ty::BrAnon(i), .. }) => {
339 let binder = &self.binders[self.binders.len() - 1 - debruijn.index()];
340 let depth = binder.lifetime_depths.start + i;
342 1 + (self.binders.last().unwrap().lifetime_depths.end - 1 - depth)
345 _ => bug!("symbol_names: non-erased region `{:?}`", region),
348 self.push_integer_62(i as u64);
352 fn print_type(mut self, ty: Ty<'tcx>) -> Result<Self::Type, Self::Error> {
353 // Basic types, never cached (single-character).
354 let basic_type = match ty.kind() {
358 ty::Tuple(_) if ty.is_unit() => "u",
359 ty::Int(IntTy::I8) => "a",
360 ty::Int(IntTy::I16) => "s",
361 ty::Int(IntTy::I32) => "l",
362 ty::Int(IntTy::I64) => "x",
363 ty::Int(IntTy::I128) => "n",
364 ty::Int(IntTy::Isize) => "i",
365 ty::Uint(UintTy::U8) => "h",
366 ty::Uint(UintTy::U16) => "t",
367 ty::Uint(UintTy::U32) => "m",
368 ty::Uint(UintTy::U64) => "y",
369 ty::Uint(UintTy::U128) => "o",
370 ty::Uint(UintTy::Usize) => "j",
371 ty::Float(FloatTy::F32) => "f",
372 ty::Float(FloatTy::F64) => "d",
375 // Placeholders (should be demangled as `_`).
376 ty::Param(_) | ty::Bound(..) | ty::Placeholder(_) | ty::Infer(_) | ty::Error(_) => "p",
380 if !basic_type.is_empty() {
381 self.push(basic_type);
385 if let Some(&i) = self.types.get(&ty) {
386 return self.print_backref(i);
388 let start = self.out.len();
391 // Basic types, handled above.
392 ty::Bool | ty::Char | ty::Str | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Never => {
395 ty::Tuple(_) if ty.is_unit() => unreachable!(),
397 // Placeholders, also handled as part of basic types.
398 ty::Param(_) | ty::Bound(..) | ty::Placeholder(_) | ty::Infer(_) | ty::Error(_) => {
402 ty::Ref(r, ty, mutbl) => {
403 self.push(match mutbl {
404 hir::Mutability::Not => "R",
405 hir::Mutability::Mut => "Q",
408 self = r.print(self)?;
410 self = ty.print(self)?;
414 self.push(match mt.mutbl {
415 hir::Mutability::Not => "P",
416 hir::Mutability::Mut => "O",
418 self = mt.ty.print(self)?;
421 ty::Array(ty, len) => {
423 self = ty.print(self)?;
424 self = self.print_const(len)?;
428 self = ty.print(self)?;
433 for ty in tys.iter() {
434 self = ty.print(self)?;
439 // Mangle all nominal types as paths.
440 ty::Adt(ty::AdtDef(Interned(&ty::AdtDefData { did: def_id, .. }, _)), substs)
441 | ty::FnDef(def_id, substs)
442 | ty::Opaque(def_id, substs)
443 | ty::Projection(ty::ProjectionTy { item_def_id: def_id, substs })
444 | ty::Closure(def_id, substs)
445 | ty::Generator(def_id, substs, _) => {
446 self = self.print_def_path(def_id, substs)?;
448 ty::Foreign(def_id) => {
449 self = self.print_def_path(def_id, &[])?;
454 self = self.in_binder(&sig, |mut cx, sig| {
455 if sig.unsafety == hir::Unsafety::Unsafe {
460 Abi::C { unwind: false } => cx.push("KC"),
463 let name = abi.name();
464 if name.contains('-') {
465 cx.push_ident(&name.replace('-', "_"));
471 for &ty in sig.inputs() {
478 sig.output().print(cx)
482 ty::Dynamic(predicates, r) => {
484 self = self.print_dyn_existential(predicates)?;
485 self = r.print(self)?;
488 ty::GeneratorWitness(_) => bug!("symbol_names: unexpected `GeneratorWitness`"),
491 // Only cache types that do not refer to an enclosing
492 // binder (which would change depending on context).
493 if !ty.has_escaping_bound_vars() {
494 self.types.insert(ty, start);
499 fn print_dyn_existential(
501 predicates: &'tcx ty::List<ty::Binder<'tcx, ty::ExistentialPredicate<'tcx>>>,
502 ) -> Result<Self::DynExistential, Self::Error> {
503 // Okay, so this is a bit tricky. Imagine we have a trait object like
504 // `dyn for<'a> Foo<'a, Bar = &'a ()>`. When we mangle this, the
505 // output looks really close to the syntax, where the `Bar = &'a ()` bit
506 // is under the same binders (`['a]`) as the `Foo<'a>` bit. However, we
507 // actually desugar these into two separate `ExistentialPredicate`s. We
508 // can't enter/exit the "binder scope" twice though, because then we
509 // would mangle the binders twice. (Also, side note, we merging these
510 // two is kind of difficult, because of potential HRTBs in the Projection
513 // Also worth mentioning: imagine that we instead had
514 // `dyn for<'a> Foo<'a, Bar = &'a ()> + Send`. In this case, `Send` is
515 // under the same binders as `Foo`. Currently, this doesn't matter,
516 // because only *auto traits* are allowed other than the principal trait
517 // and all auto traits don't have any generics. Two things could
518 // make this not an "okay" mangling:
519 // 1) Instead of mangling only *used*
520 // bound vars, we want to mangle *all* bound vars (`for<'b> Send` is a
521 // valid trait predicate);
522 // 2) We allow multiple "principal" traits in the future, or at least
523 // allow in any form another trait predicate that can take generics.
525 // Here we assume that predicates have the following structure:
526 // [<Trait> [{<Projection>}]] [{<Auto>}]
527 // Since any predicates after the first one shouldn't change the binders,
528 // just put them all in the binders of the first.
529 self = self.in_binder(&predicates[0], |mut cx, _| {
530 for predicate in predicates.iter() {
531 // It would be nice to be able to validate bound vars here, but
532 // projections can actually include bound vars from super traits
533 // because of HRTBs (only in the `Self` type). Also, auto traits
534 // could have different bound vars *anyways*.
535 match predicate.as_ref().skip_binder() {
536 ty::ExistentialPredicate::Trait(trait_ref) => {
537 // Use a type that can't appear in defaults of type parameters.
538 let dummy_self = cx.tcx.mk_ty_infer(ty::FreshTy(0));
539 let trait_ref = trait_ref.with_self_ty(cx.tcx, dummy_self);
540 cx = cx.print_def_path(trait_ref.def_id, trait_ref.substs)?;
542 ty::ExistentialPredicate::Projection(projection) => {
543 let name = cx.tcx.associated_item(projection.item_def_id).name;
545 cx.push_ident(name.as_str());
546 cx = match projection.term {
547 ty::Term::Ty(ty) => ty.print(cx),
548 ty::Term::Const(c) => c.print(cx),
551 ty::ExistentialPredicate::AutoTrait(def_id) => {
552 cx = cx.print_def_path(*def_id, &[])?;
563 fn print_const(mut self, ct: ty::Const<'tcx>) -> Result<Self::Const, Self::Error> {
564 // We only mangle a typed value if the const can be evaluated.
565 let ct = ct.eval(self.tcx, ty::ParamEnv::reveal_all());
567 ty::ConstKind::Value(_) => {}
569 // Placeholders (should be demangled as `_`).
570 // NOTE(eddyb) despite `Unevaluated` having a `DefId` (and therefore
571 // a path), even for it we still need to encode a placeholder, as
572 // the path could refer back to e.g. an `impl` using the constant.
573 ty::ConstKind::Unevaluated(_)
574 | ty::ConstKind::Param(_)
575 | ty::ConstKind::Infer(_)
576 | ty::ConstKind::Bound(..)
577 | ty::ConstKind::Placeholder(_)
578 | ty::ConstKind::Error(_) => {
579 // Never cached (single-character).
585 if let Some(&i) = self.consts.get(&ct) {
586 return self.print_backref(i);
589 let start = self.out.len();
593 ty::Uint(_) | ty::Int(_) | ty::Bool | ty::Char => {
594 self = ty.print(self)?;
596 let mut bits = ct.eval_bits(self.tcx, ty::ParamEnv::reveal_all(), ty);
598 // Negative integer values are mangled using `n` as a "sign prefix".
599 if let ty::Int(ity) = ty.kind() {
601 Integer::from_int_ty(&self.tcx, *ity).size().sign_extend(bits) as i128;
605 bits = val.unsigned_abs();
608 let _ = write!(self.out, "{:x}_", bits);
611 // FIXME(valtrees): Remove the special case for `str`
612 // here and fully support unsized constants.
613 ty::Ref(_, inner_ty, mutbl) => {
614 self.push(match mutbl {
615 hir::Mutability::Not => "R",
616 hir::Mutability::Mut => "Q",
619 match inner_ty.kind() {
620 ty::Str if *mutbl == hir::Mutability::Not => {
622 ty::ConstKind::Value(valtree) => {
624 valtree.try_to_raw_bytes(self.tcx(), ty).unwrap_or_else(|| {
626 "expected to get raw bytes from valtree {:?} for type {:}",
630 let s = std::str::from_utf8(slice).expect("non utf8 str from miri");
634 // FIXME(eddyb) use a specialized hex-encoding loop.
635 for byte in s.bytes() {
636 let _ = write!(self.out, "{:02x}", byte);
643 bug!("symbol_names: unsupported `&str` constant: {:?}", ct);
651 .expect("tried to dereference on non-ptr type")
653 let dereferenced_const =
654 self.tcx.mk_const(ty::ConstS { kind: ct.kind(), ty: pointee_ty });
655 self = dereferenced_const.print(self)?;
660 ty::Array(..) | ty::Tuple(..) | ty::Adt(..) | ty::Slice(_) => {
661 let contents = self.tcx.destructure_const(ct);
662 let fields = contents.fields.iter().copied();
664 let print_field_list = |mut this: Self| {
665 for field in fields.clone() {
666 this = field.print(this)?;
672 match *ct.ty().kind() {
673 ty::Array(..) | ty::Slice(_) => {
675 self = print_field_list(self)?;
679 self = print_field_list(self)?;
681 ty::Adt(def, substs) => {
683 contents.variant.expect("destructed const of adt without variant idx");
684 let variant_def = &def.variant(variant_idx);
687 self = self.print_def_path(variant_def.def_id, substs)?;
689 match variant_def.ctor_kind {
695 self = print_field_list(self)?;
697 CtorKind::Fictive => {
699 for (field_def, field) in iter::zip(&variant_def.fields, fields) {
700 // HACK(eddyb) this mimics `path_append`,
701 // instead of simply using `field_def.ident`,
702 // just to be able to handle disambiguators.
703 let disambiguated_field =
704 self.tcx.def_key(field_def.did).disambiguated_data;
705 let field_name = disambiguated_field.data.get_opt_name();
706 self.push_disambiguator(
707 disambiguated_field.disambiguator as u64,
709 self.push_ident(field_name.unwrap_or(kw::Empty).as_str());
711 self = field.print(self)?;
721 bug!("symbol_names: unsupported constant of type `{}` ({:?})", ct.ty(), ct);
725 // Only cache consts that do not refer to an enclosing
726 // binder (which would change depending on context).
727 if !ct.has_escaping_bound_vars() {
728 self.consts.insert(ct, start);
733 fn path_crate(self, cnum: CrateNum) -> Result<Self::Path, Self::Error> {
735 let stable_crate_id = self.tcx.def_path_hash(cnum.as_def_id()).stable_crate_id();
736 self.push_disambiguator(stable_crate_id.to_u64());
737 let name = self.tcx.crate_name(cnum);
738 self.push_ident(name.as_str());
745 trait_ref: Option<ty::TraitRef<'tcx>>,
746 ) -> Result<Self::Path, Self::Error> {
747 assert!(trait_ref.is_some());
748 let trait_ref = trait_ref.unwrap();
751 self = self_ty.print(self)?;
752 self.print_def_path(trait_ref.def_id, trait_ref.substs)
757 _: impl FnOnce(Self) -> Result<Self::Path, Self::Error>,
758 _: &DisambiguatedDefPathData,
760 _: Option<ty::TraitRef<'tcx>>,
761 ) -> Result<Self::Path, Self::Error> {
762 // Inlined into `print_impl_path`
768 print_prefix: impl FnOnce(Self) -> Result<Self::Path, Self::Error>,
769 disambiguated_data: &DisambiguatedDefPathData,
770 ) -> Result<Self::Path, Self::Error> {
771 let ns = match disambiguated_data.data {
772 // Extern block segments can be skipped, names from extern blocks
773 // are effectively living in their parent modules.
774 DefPathData::ForeignMod => return print_prefix(self),
776 // Uppercase categories are more stable than lowercase ones.
777 DefPathData::TypeNs(_) => 't',
778 DefPathData::ValueNs(_) => 'v',
779 DefPathData::ClosureExpr => 'C',
780 DefPathData::Ctor => 'c',
781 DefPathData::AnonConst => 'k',
782 DefPathData::ImplTrait => 'i',
784 // These should never show up as `path_append` arguments.
785 DefPathData::CrateRoot
787 | DefPathData::GlobalAsm
789 | DefPathData::MacroNs(_)
790 | DefPathData::LifetimeNs(_) => {
791 bug!("symbol_names: unexpected DefPathData: {:?}", disambiguated_data.data)
795 let name = disambiguated_data.data.get_opt_name();
800 disambiguated_data.disambiguator as u64,
801 name.unwrap_or(kw::Empty).as_str(),
805 fn path_generic_args(
807 print_prefix: impl FnOnce(Self) -> Result<Self::Path, Self::Error>,
808 args: &[GenericArg<'tcx>],
809 ) -> Result<Self::Path, Self::Error> {
810 // Don't print any regions if they're all erased.
811 let print_regions = args.iter().any(|arg| match arg.unpack() {
812 GenericArgKind::Lifetime(r) => !r.is_erased(),
815 let args = args.iter().cloned().filter(|arg| match arg.unpack() {
816 GenericArgKind::Lifetime(_) => print_regions,
820 if args.clone().next().is_none() {
821 return print_prefix(self);
825 self = print_prefix(self)?;
828 GenericArgKind::Lifetime(lt) => {
829 self = lt.print(self)?;
831 GenericArgKind::Type(ty) => {
832 self = ty.print(self)?;
834 GenericArgKind::Const(c) => {
836 self = c.print(self)?;