1use alloc::{string::String, vec::Vec};
15use core::fmt;
16
17use hir_lang::{BinderId, Def, DefId, Effects, ItemId, Prim, Symbol, TyId, UnitId, VariantId};
18use intern_lang::Lookup;
19
20#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
38pub struct TypeId(u32);
39
40const PRIMS: [Prim; 15] = [
43 Prim::Bool,
44 Prim::I8,
45 Prim::I16,
46 Prim::I32,
47 Prim::I64,
48 Prim::Isize,
49 Prim::U8,
50 Prim::U16,
51 Prim::U32,
52 Prim::U64,
53 Prim::Usize,
54 Prim::F32,
55 Prim::F64,
56 Prim::Char,
57 Prim::Str,
58];
59
60const FIRST_PRIM: u32 = 5;
62
63const fn prim_code(p: Prim) -> u8 {
64 match p {
65 Prim::Bool => 0,
66 Prim::I8 => 1,
67 Prim::I16 => 2,
68 Prim::I32 => 3,
69 Prim::I64 => 4,
70 Prim::Isize => 5,
71 Prim::U8 => 6,
72 Prim::U16 => 7,
73 Prim::U32 => 8,
74 Prim::U64 => 9,
75 Prim::Usize => 10,
76 Prim::F32 => 11,
77 Prim::F64 => 12,
78 Prim::Char => 13,
79 Prim::Str => 14,
80 }
81}
82
83impl TypeId {
84 pub const ERROR: Self = Self(0);
88 pub const ANY: Self = Self(1);
90 pub const NEVER: Self = Self(2);
93 pub const NULL: Self = Self(3);
95 pub const UNIT: Self = Self(4);
97
98 #[must_use]
110 pub const fn prim(p: Prim) -> Self {
111 Self(FIRST_PRIM + prim_code(p) as u32)
112 }
113
114 #[must_use]
124 pub const fn index(self) -> usize {
125 self.0 as usize
126 }
127
128 pub(crate) const fn raw(self) -> u32 {
129 self.0
130 }
131
132 pub(crate) const fn from_raw(raw: u32) -> Self {
133 Self(raw)
134 }
135}
136
137impl fmt::Debug for TypeId {
138 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
139 write!(f, "TypeId({})", self.0)
140 }
141}
142
143#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
158pub struct Field {
159 pub name: Symbol,
161 pub ty: TypeId,
163}
164
165#[derive(Clone, Copy, Debug, PartialEq, Eq)]
181#[non_exhaustive]
182pub enum Type<'a> {
183 Error,
185 Any,
187 Never,
189 Null,
191 Prim(Prim),
193 Tuple(&'a [TypeId]),
195 Array {
197 elem: TypeId,
199 len: u64,
201 },
202 ParamArray {
205 elem: TypeId,
207 len: TypeId,
209 },
210 Slice(TypeId),
212 Ref {
214 mutable: bool,
216 inner: TypeId,
218 },
219 Ptr {
221 mutable: bool,
223 inner: TypeId,
225 },
226 Fn {
228 params: &'a [TypeId],
230 ret: TypeId,
232 effects: Effects,
234 },
235 Nullable(TypeId),
237 Map {
239 key: TypeId,
241 value: TypeId,
243 },
244 Record(&'a [Field]),
246 Adt {
249 item: ItemId,
251 args: &'a [TypeId],
254 },
255 Foreign {
257 def: DefId,
259 args: &'a [TypeId],
261 },
262 Extern {
265 name: Symbol,
267 args: &'a [TypeId],
269 },
270 Param(BinderId),
272 ImplParam(TyId),
275 SelfOf(ItemId),
277 Union(&'a [TypeId]),
280 Intersection(&'a [TypeId]),
282 Trait {
285 item: ItemId,
287 args: &'a [TypeId],
290 },
291 Dyn(&'a [TypeId]),
294 Projection {
297 interface: ItemId,
299 assoc: ItemId,
301 args: &'a [TypeId],
303 },
304 Opaque {
307 origin: TyId,
309 args: &'a [TypeId],
311 },
312 Const(i64),
314 Async(TypeId),
316 Task(TypeId),
318 Generator {
320 item: TypeId,
322 is_async: bool,
324 },
325}
326
327#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
329#[repr(u8)]
330pub(crate) enum Tag {
331 Error,
332 Any,
333 Never,
334 Null,
335 Tuple,
336 Prim,
337 Array,
338 Slice,
339 Ref,
340 Ptr,
341 Fn,
342 Nullable,
343 Map,
344 Record,
345 Adt,
346 Foreign,
347 Extern,
348 Param,
349 ImplParam,
350 SelfOf,
351 Union,
352 Inter,
353 Trait,
354 Dyn,
355 Proj,
356 Opaque,
357 Const,
358 Async,
359 Task,
360 Gen,
361 AsyncGen,
362 Var,
363}
364
365impl Tag {
366 const fn pooled(self) -> bool {
368 matches!(
369 self,
370 Tag::Tuple
371 | Tag::Adt
372 | Tag::Foreign
373 | Tag::Extern
374 | Tag::Union
375 | Tag::Inter
376 | Tag::Trait
377 | Tag::Dyn
378 | Tag::Proj
379 | Tag::Opaque
380 )
381 }
382
383 const fn one_child(self) -> bool {
385 matches!(
386 self,
387 Tag::Slice
388 | Tag::Ref
389 | Tag::Ptr
390 | Tag::Nullable
391 | Tag::Async
392 | Tag::Task
393 | Tag::Gen
394 | Tag::AsyncGen
395 )
396 }
397
398 pub(crate) const fn is_placeholder(self) -> bool {
400 matches!(self, Tag::Param | Tag::ImplParam | Tag::SelfOf)
401 }
402}
403
404#[derive(Clone, Copy, Debug, PartialEq, Eq)]
407pub(crate) struct Node {
408 pub(crate) tag: Tag,
409 pub(crate) small: u8,
411 pub(crate) has_var: bool,
413 pub(crate) has_param: bool,
416 pub(crate) has_proj: bool,
418 pub(crate) x: u32,
419 pub(crate) y: u32,
420 pub(crate) z: u32,
421 pub(crate) start: u32,
422 pub(crate) len: u32,
423}
424
425impl Node {
426 const fn leaf(tag: Tag) -> Self {
427 Self {
428 tag,
429 small: 0,
430 has_var: false,
431 has_param: false,
432 has_proj: false,
433 x: 0,
434 y: 0,
435 z: 0,
436 start: 0,
437 len: 0,
438 }
439 }
440}
441
442struct Key<'k> {
445 tag: Tag,
446 small: u8,
447 x: u32,
448 y: u32,
449 z: u32,
450 kids: &'k [TypeId],
451 fields: &'k [Field],
452}
453
454const EMPTY: u32 = u32::MAX;
455
456pub(crate) fn effects_bits(e: Effects) -> u8 {
457 let mut bits = 0u8;
458 for (i, flag) in [
459 Effects::THROWS,
460 Effects::ASYNC,
461 Effects::YIELD,
462 Effects::UNSAFE,
463 ]
464 .into_iter()
465 .enumerate()
466 {
467 if e.contains(flag) {
468 bits |= 1 << i;
469 }
470 }
471 bits
472}
473
474pub(crate) fn effects_from_bits(bits: u8) -> Effects {
475 let mut e = Effects::NONE;
476 for (i, flag) in [
477 Effects::THROWS,
478 Effects::ASYNC,
479 Effects::YIELD,
480 Effects::UNSAFE,
481 ]
482 .into_iter()
483 .enumerate()
484 {
485 if bits & (1 << i) != 0 {
486 e = e.union(flag);
487 }
488 }
489 e
490}
491
492fn raw_of(index: usize) -> u32 {
493 u32::try_from(index).unwrap_or(u32::MAX)
494}
495
496#[derive(Clone, Debug, PartialEq, Eq)]
520pub struct Types {
521 nodes: Vec<Node>,
522 kids: Vec<TypeId>,
523 fields: Vec<Field>,
524 table: Vec<u32>,
526 interned: usize,
528 item_names: Vec<u32>,
531 binder_names: Vec<u32>,
532 impl_names: Vec<u32>,
533}
534
535fn set_name(names: &mut Vec<u32>, index: usize, name: Symbol) {
536 if index >= names.len() {
537 names.resize(index + 1, 0);
538 }
539 if let Some(slot) = names.get_mut(index) {
540 *slot = name.as_u32();
541 }
542}
543
544impl Default for Types {
545 fn default() -> Self {
546 Self::new()
547 }
548}
549
550impl Types {
551 #[must_use]
562 pub fn new() -> Self {
563 let mut types = Self {
564 nodes: Vec::with_capacity(64),
565 kids: Vec::new(),
566 fields: Vec::new(),
567 table: alloc::vec![EMPTY; 64],
568 interned: 0,
569 item_names: Vec::new(),
570 binder_names: Vec::new(),
571 impl_names: Vec::new(),
572 };
573 for tag in [Tag::Error, Tag::Any, Tag::Never, Tag::Null] {
575 let _ = types.simple(tag, 0, 0, 0, 0);
576 }
577 let _ = types.tuple(&[]);
578 for p in PRIMS {
579 let _ = types.simple(Tag::Prim, prim_code(p), 0, 0, 0);
580 }
581 types
582 }
583
584 #[must_use]
597 pub fn len(&self) -> usize {
598 self.nodes.len()
599 }
600
601 #[must_use]
610 pub fn is_empty(&self) -> bool {
611 self.nodes.is_empty()
612 }
613
614 pub(crate) fn footprint(&self) -> usize {
617 self.nodes.len() + self.kids.len() + self.fields.len()
618 }
619
620 pub(crate) fn node(&self, id: TypeId) -> Node {
623 self.nodes
624 .get(id.index())
625 .copied()
626 .unwrap_or(Node::leaf(Tag::Error))
627 }
628
629 pub(crate) fn kids_of(&self, n: &Node) -> &[TypeId] {
630 if n.tag == Tag::Record {
631 return &[];
632 }
633 let start = n.start as usize;
634 self.kids
635 .get(start..start.saturating_add(n.len as usize))
636 .unwrap_or(&[])
637 }
638
639 pub(crate) fn fields_of(&self, n: &Node) -> &[Field] {
640 if n.tag != Tag::Record {
641 return &[];
642 }
643 let start = n.start as usize;
644 self.fields
645 .get(start..start.saturating_add(n.len as usize))
646 .unwrap_or(&[])
647 }
648
649 pub(crate) fn kids(&self, id: TypeId) -> &[TypeId] {
651 let n = self.node(id);
652 self.kids_of(&n)
653 }
654
655 pub(crate) fn for_each_child(&self, id: TypeId, mut f: impl FnMut(TypeId)) {
658 let n = self.node(id);
659 match n.tag {
660 t if t.pooled() => self.kids_of(&n).iter().for_each(|&k| f(k)),
661 Tag::Fn => {
662 self.kids_of(&n).iter().for_each(|&k| f(k));
663 f(TypeId(n.z));
664 }
665 Tag::Record => self.fields_of(&n).iter().for_each(|fl| f(fl.ty)),
666 t if t.one_child() => f(TypeId(n.x)),
667 Tag::Map | Tag::Array => {
668 f(TypeId(n.x));
669 f(TypeId(n.y));
670 }
671 _ => {}
672 }
673 }
674
675 #[must_use]
688 pub fn get(&self, id: TypeId) -> Type<'_> {
689 let n = self.node(id);
690 let kids = || self.kids_of_ref(id);
691 match n.tag {
692 Tag::Error | Tag::Var => Type::Error,
693 Tag::Any => Type::Any,
694 Tag::Never => Type::Never,
695 Tag::Null => Type::Null,
696 Tag::Prim => Type::Prim(
697 PRIMS
698 .get(usize::from(n.small))
699 .copied()
700 .unwrap_or(Prim::Bool),
701 ),
702 Tag::Tuple => Type::Tuple(kids()),
703 Tag::Array => {
704 let len = self.node(TypeId(n.y));
705 if len.tag == Tag::Const {
706 Type::Array {
707 elem: TypeId(n.x),
708 len: const_value(&len) as u64,
709 }
710 } else {
711 Type::ParamArray {
712 elem: TypeId(n.x),
713 len: TypeId(n.y),
714 }
715 }
716 }
717 Tag::Slice => Type::Slice(TypeId(n.x)),
718 Tag::Ref => Type::Ref {
719 mutable: n.small != 0,
720 inner: TypeId(n.x),
721 },
722 Tag::Ptr => Type::Ptr {
723 mutable: n.small != 0,
724 inner: TypeId(n.x),
725 },
726 Tag::Fn => Type::Fn {
727 params: kids(),
728 ret: TypeId(n.z),
729 effects: effects_from_bits(n.small),
730 },
731 Tag::Nullable => Type::Nullable(TypeId(n.x)),
732 Tag::Map => Type::Map {
733 key: TypeId(n.x),
734 value: TypeId(n.y),
735 },
736 Tag::Record => Type::Record(self.fields_of_ref(id)),
737 Tag::Adt => ItemId::from_index(n.x as usize)
738 .map_or(Type::Error, |item| Type::Adt { item, args: kids() }),
739 Tag::Foreign => {
740 foreign_def(&n).map_or(Type::Error, |def| Type::Foreign { def, args: kids() })
741 }
742 Tag::Extern => Symbol::from_u32(n.x)
743 .map_or(Type::Error, |name| Type::Extern { name, args: kids() }),
744 Tag::Param => BinderId::from_index(n.x as usize).map_or(Type::Error, Type::Param),
745 Tag::ImplParam => TyId::from_index(n.x as usize).map_or(Type::Error, Type::ImplParam),
746 Tag::SelfOf => ItemId::from_index(n.x as usize).map_or(Type::Error, Type::SelfOf),
747 Tag::Union => Type::Union(kids()),
748 Tag::Inter => Type::Intersection(kids()),
749 Tag::Trait => ItemId::from_index(n.x as usize)
750 .map_or(Type::Error, |item| Type::Trait { item, args: kids() }),
751 Tag::Dyn => Type::Dyn(kids()),
752 Tag::Proj => match (
753 ItemId::from_index(n.x as usize),
754 ItemId::from_index(n.y as usize),
755 ) {
756 (Some(interface), Some(assoc)) => Type::Projection {
757 interface,
758 assoc,
759 args: kids(),
760 },
761 _ => Type::Error,
762 },
763 Tag::Opaque => {
764 TyId::from_index(n.x as usize).map_or(Type::Error, |origin| Type::Opaque {
765 origin,
766 args: kids(),
767 })
768 }
769 Tag::Const => Type::Const(const_value(&n)),
770 Tag::Async => Type::Async(TypeId(n.x)),
771 Tag::Task => Type::Task(TypeId(n.x)),
772 Tag::Gen => Type::Generator {
773 item: TypeId(n.x),
774 is_async: false,
775 },
776 Tag::AsyncGen => Type::Generator {
777 item: TypeId(n.x),
778 is_async: true,
779 },
780 }
781 }
782
783 fn kids_of_ref(&self, id: TypeId) -> &[TypeId] {
784 let n = self.node(id);
785 self.kids_of(&n)
786 }
787
788 fn fields_of_ref(&self, id: TypeId) -> &[Field] {
789 let n = self.node(id);
790 self.fields_of(&n)
791 }
792
793 fn hash(key: &Key<'_>) -> u64 {
796 const K: u64 = 0x51_7c_c1_b7_27_22_0a_95;
799 let mut h = 0u64;
800 let mut add = |v: u64| h = (h.rotate_left(5) ^ v).wrapping_mul(K);
801 add(key.tag as u64);
802 add(u64::from(key.small));
803 add(u64::from(key.x));
804 add(u64::from(key.y));
805 add(u64::from(key.z));
806 add(key.kids.len() as u64);
807 for k in key.kids {
808 add(u64::from(k.0));
809 }
810 add(key.fields.len() as u64);
811 for f in key.fields {
812 add(u64::from(f.name.as_u32()));
813 add(u64::from(f.ty.0));
814 }
815 h
816 }
817
818 fn matches(&self, n: &Node, key: &Key<'_>) -> bool {
819 n.tag == key.tag
820 && n.small == key.small
821 && n.x == key.x
822 && n.y == key.y
823 && n.z == key.z
824 && if n.tag == Tag::Record {
825 key.kids.is_empty() && self.fields_of(n) == key.fields
826 } else {
827 key.fields.is_empty() && self.kids_of(n) == key.kids
828 }
829 }
830
831 fn intern(&mut self, key: Key<'_>) -> TypeId {
832 let hash = Self::hash(&key);
833 let mask = self.table.len() - 1;
834 let mut slot = (hash as usize) & mask;
835 loop {
836 match self.table.get(slot).copied() {
837 Some(EMPTY) | None => break,
838 Some(existing) => {
839 if let Some(n) = self.nodes.get(existing as usize) {
840 if self.matches(n, &key) {
841 return TypeId(existing);
842 }
843 }
844 }
845 }
846 slot = (slot + 1) & mask;
847 }
848 let id = self.push(&key);
849 if let Some(s) = self.table.get_mut(slot) {
850 *s = id.0;
851 }
852 self.interned += 1;
853 if self.interned * 2 > self.table.len() {
854 self.grow();
855 }
856 id
857 }
858
859 fn push(&mut self, key: &Key<'_>) -> TypeId {
860 let mut has_var = key.tag == Tag::Var;
861 let mut has_param = key.tag.is_placeholder();
862 let mut has_proj = key.tag == Tag::Proj;
863 let mut note = |n: Node| {
864 has_var |= n.has_var;
865 has_param |= n.has_param;
866 has_proj |= n.has_proj;
867 };
868 for &k in key.kids {
869 note(self.node(k));
870 }
871 for f in key.fields {
872 note(self.node(f.ty));
873 }
874 for raw in self.scalar_children(key) {
875 note(self.node(TypeId(raw)));
876 }
877 let (start, len) = if key.fields.is_empty() {
878 let start = self.kids.len();
879 self.kids.extend_from_slice(key.kids);
880 (start, key.kids.len())
881 } else {
882 let start = self.fields.len();
883 self.fields.extend_from_slice(key.fields);
884 (start, key.fields.len())
885 };
886 let id = TypeId(raw_of(self.nodes.len()));
887 self.nodes.push(Node {
888 tag: key.tag,
889 small: key.small,
890 has_var,
891 has_param,
892 has_proj,
893 x: key.x,
894 y: key.y,
895 z: key.z,
896 start: raw_of(start),
897 len: u32::try_from(len).unwrap_or(0),
898 });
899 id
900 }
901
902 fn scalar_children(&self, key: &Key<'_>) -> impl Iterator<Item = u32> {
905 let (a, b) = match key.tag {
906 t if t.one_child() => (Some(key.x), None),
907 Tag::Map | Tag::Array => (Some(key.x), Some(key.y)),
908 Tag::Fn => (Some(key.z), None),
909 _ => (None, None),
910 };
911 a.into_iter().chain(b)
912 }
913
914 fn grow(&mut self) {
915 let cap = self.table.len() * 2;
916 let mut table = alloc::vec![EMPTY; cap];
917 let mask = cap - 1;
918 for (i, n) in self.nodes.iter().enumerate() {
919 if n.tag == Tag::Var {
920 continue;
921 }
922 let key = Key {
923 tag: n.tag,
924 small: n.small,
925 x: n.x,
926 y: n.y,
927 z: n.z,
928 kids: self.kids_of(n),
929 fields: self.fields_of(n),
930 };
931 let mut slot = (Self::hash(&key) as usize) & mask;
932 while table.get(slot).is_some_and(|&s| s != EMPTY) {
933 slot = (slot + 1) & mask;
934 }
935 if let Some(s) = table.get_mut(slot) {
936 *s = raw_of(i);
937 }
938 }
939 self.table = table;
940 }
941
942 fn simple(&mut self, tag: Tag, small: u8, x: u32, y: u32, z: u32) -> TypeId {
943 self.intern(Key {
944 tag,
945 small,
946 x,
947 y,
948 z,
949 kids: &[],
950 fields: &[],
951 })
952 }
953
954 fn pooled(&mut self, tag: Tag, x: u32, y: u32, kids: &[TypeId]) -> TypeId {
955 self.intern(Key {
956 tag,
957 small: 0,
958 x,
959 y,
960 z: 0,
961 kids,
962 fields: &[],
963 })
964 }
965
966 pub(crate) fn fresh_var(&mut self, class: u8) -> TypeId {
969 let n = raw_of(self.nodes.len());
970 self.push(&Key {
971 tag: Tag::Var,
972 small: class,
973 x: n,
974 y: 0,
975 z: 0,
976 kids: &[],
977 fields: &[],
978 })
979 }
980
981 pub fn tuple(&mut self, elems: &[TypeId]) -> TypeId {
993 self.pooled(Tag::Tuple, 0, 0, elems)
994 }
995
996 pub fn array(&mut self, elem: TypeId, len: u64) -> TypeId {
1009 let len = self.constant(len as i64);
1010 self.array_of(elem, len)
1011 }
1012
1013 pub(crate) fn array_of(&mut self, elem: TypeId, len: TypeId) -> TypeId {
1016 self.simple(Tag::Array, 0, elem.0, len.0, 0)
1017 }
1018
1019 pub fn slice(&mut self, elem: TypeId) -> TypeId {
1031 self.simple(Tag::Slice, 0, elem.0, 0, 0)
1032 }
1033
1034 pub fn reference(&mut self, mutable: bool, inner: TypeId) -> TypeId {
1046 self.simple(Tag::Ref, u8::from(mutable), inner.0, 0, 0)
1047 }
1048
1049 pub fn pointer(&mut self, mutable: bool, inner: TypeId) -> TypeId {
1061 self.simple(Tag::Ptr, u8::from(mutable), inner.0, 0, 0)
1062 }
1063
1064 pub fn func(&mut self, params: &[TypeId], ret: TypeId, effects: Effects) -> TypeId {
1077 self.intern(Key {
1078 tag: Tag::Fn,
1079 small: effects_bits(effects),
1080 x: 0,
1081 y: 0,
1082 z: ret.0,
1083 kids: params,
1084 fields: &[],
1085 })
1086 }
1087
1088 pub fn nullable(&mut self, inner: TypeId) -> TypeId {
1101 match self.node(inner).tag {
1102 Tag::Nullable | Tag::Null | Tag::Error | Tag::Any => inner,
1103 Tag::Never => TypeId::NULL,
1104 _ => self.simple(Tag::Nullable, 0, inner.0, 0, 0),
1105 }
1106 }
1107
1108 pub fn map(&mut self, key: TypeId, value: TypeId) -> TypeId {
1121 self.simple(Tag::Map, 0, key.0, value.0, 0)
1122 }
1123
1124 pub fn record(&mut self, fields: &[Field]) -> TypeId {
1141 let mut sorted: Vec<Field> = fields.to_vec();
1142 sorted.sort_by_key(|f| f.name);
1143 sorted.dedup_by_key(|f| f.name);
1144 self.record_sorted(&sorted)
1145 }
1146
1147 pub(crate) fn record_sorted(&mut self, sorted: &[Field]) -> TypeId {
1148 if sorted.is_empty() {
1149 return self.simple(Tag::Record, 0, 0, 0, 0);
1153 }
1154 self.intern(Key {
1155 tag: Tag::Record,
1156 small: 0,
1157 x: 0,
1158 y: 0,
1159 z: 0,
1160 kids: &[],
1161 fields: sorted,
1162 })
1163 }
1164
1165 pub fn adt(&mut self, item: ItemId) -> TypeId {
1180 self.adt_with(item, &[])
1181 }
1182
1183 pub fn adt_with(&mut self, item: ItemId, args: &[TypeId]) -> TypeId {
1200 self.pooled(Tag::Adt, raw_of(item.index()), 0, args)
1201 }
1202
1203 pub(crate) fn name_item(&mut self, item: ItemId, name: Symbol) {
1205 set_name(&mut self.item_names, item.index(), name);
1206 }
1207
1208 pub(crate) fn name_binder(&mut self, binder: BinderId, name: Symbol) {
1210 set_name(&mut self.binder_names, binder.index(), name);
1211 }
1212
1213 pub(crate) fn name_impl(&mut self, ty: TyId, name: Symbol) {
1216 set_name(&mut self.impl_names, ty.index(), name);
1217 }
1218
1219 pub fn foreign(&mut self, def: DefId) -> TypeId {
1234 self.foreign_with(def, &[])
1235 }
1236
1237 pub fn foreign_with(&mut self, def: DefId, args: &[TypeId]) -> TypeId {
1252 let (kind, index) = match def.def() {
1253 Def::Item(i) => (0, i.index()),
1254 Def::Variant(v) => (1, v.index()),
1255 };
1256 self.intern(Key {
1257 tag: Tag::Foreign,
1258 small: kind,
1259 x: def.unit().as_u32(),
1260 y: raw_of(index),
1261 z: 0,
1262 kids: args,
1263 fields: &[],
1264 })
1265 }
1266
1267 pub fn external(&mut self, name: Symbol) -> TypeId {
1283 self.external_with(name, &[])
1284 }
1285
1286 pub fn external_with(&mut self, name: Symbol, args: &[TypeId]) -> TypeId {
1302 self.pooled(Tag::Extern, name.as_u32(), 0, args)
1303 }
1304
1305 pub(crate) fn param(&mut self, binder: BinderId) -> TypeId {
1306 self.simple(Tag::Param, 0, raw_of(binder.index()), 0, 0)
1307 }
1308
1309 pub(crate) fn impl_param(&mut self, ty: TyId) -> TypeId {
1310 self.simple(Tag::ImplParam, 0, raw_of(ty.index()), 0, 0)
1311 }
1312
1313 pub(crate) fn self_of(&mut self, item: ItemId) -> TypeId {
1314 self.simple(Tag::SelfOf, 0, raw_of(item.index()), 0, 0)
1315 }
1316
1317 pub(crate) fn trait_ref(&mut self, item: ItemId, args: &[TypeId]) -> TypeId {
1318 self.pooled(Tag::Trait, raw_of(item.index()), 0, args)
1319 }
1320
1321 pub(crate) fn dyn_of(&mut self, traits: &[TypeId]) -> TypeId {
1323 let mut sorted = traits.to_vec();
1324 sorted.sort_unstable();
1325 sorted.dedup();
1326 self.pooled(Tag::Dyn, 0, 0, &sorted)
1327 }
1328
1329 pub(crate) fn projection(
1331 &mut self,
1332 interface: ItemId,
1333 assoc: ItemId,
1334 args: &[TypeId],
1335 ) -> TypeId {
1336 self.pooled(
1337 Tag::Proj,
1338 raw_of(interface.index()),
1339 raw_of(assoc.index()),
1340 args,
1341 )
1342 }
1343
1344 pub(crate) fn opaque(&mut self, origin: TyId, args: &[TypeId]) -> TypeId {
1345 self.pooled(Tag::Opaque, raw_of(origin.index()), 0, args)
1346 }
1347
1348 pub(crate) fn constant(&mut self, value: i64) -> TypeId {
1349 let bits = value as u64;
1350 self.simple(Tag::Const, 0, bits as u32, (bits >> 32) as u32, 0)
1351 }
1352
1353 pub fn union(&mut self, members: &[TypeId]) -> TypeId {
1374 let mut flat: Vec<TypeId> = Vec::with_capacity(members.len());
1375 let mut nullable = false;
1376 for &m in members {
1377 let n = self.node(m);
1378 match n.tag {
1379 Tag::Error | Tag::Any => return m,
1380 Tag::Never => {}
1381 Tag::Null => nullable = true,
1382 Tag::Nullable => {
1383 nullable = true;
1384 let inner = TypeId(n.x);
1385 match self.node(inner).tag {
1386 Tag::Union => flat.extend_from_slice(self.kids(inner)),
1387 _ => flat.push(inner),
1388 }
1389 }
1390 Tag::Union => flat.extend_from_slice(self.kids_of(&n)),
1391 _ => flat.push(m),
1392 }
1393 }
1394 flat.sort_unstable();
1395 flat.dedup();
1396 let body = match flat.as_slice() {
1397 [] => TypeId::NEVER,
1398 [one] => *one,
1399 _ => self.pooled(Tag::Union, 0, 0, &flat),
1400 };
1401 if nullable { self.nullable(body) } else { body }
1402 }
1403
1404 pub fn intersection(&mut self, members: &[TypeId]) -> TypeId {
1422 let mut flat: Vec<TypeId> = Vec::with_capacity(members.len());
1423 for &m in members {
1424 let n = self.node(m);
1425 match n.tag {
1426 Tag::Error | Tag::Never => return m,
1427 Tag::Inter => flat.extend_from_slice(self.kids_of(&n)),
1428 _ => flat.push(m),
1429 }
1430 }
1431 flat.sort_unstable();
1432 flat.dedup();
1433 match flat.as_slice() {
1434 [] => TypeId::ANY,
1435 [one] => *one,
1436 _ => self.pooled(Tag::Inter, 0, 0, &flat),
1437 }
1438 }
1439
1440 pub fn awaitable(&mut self, result: TypeId) -> TypeId {
1452 self.simple(Tag::Async, 0, result.0, 0, 0)
1453 }
1454
1455 pub fn task(&mut self, result: TypeId) -> TypeId {
1467 self.simple(Tag::Task, 0, result.0, 0, 0)
1468 }
1469
1470 pub fn generator(&mut self, item: TypeId, is_async: bool) -> TypeId {
1482 let tag = if is_async { Tag::AsyncGen } else { Tag::Gen };
1483 self.simple(tag, 0, item.0, 0, 0)
1484 }
1485
1486 pub(crate) fn rebuild(&mut self, id: TypeId, kids: &[TypeId]) -> TypeId {
1490 let n = self.node(id);
1491 let first = |i: usize| kids.get(i).copied().unwrap_or(TypeId::ERROR);
1492 match n.tag {
1493 Tag::Union => self.union(kids),
1494 Tag::Inter => self.intersection(kids),
1495 Tag::Dyn => self.dyn_of(kids),
1496 t if t.pooled() => self.intern(Key {
1497 tag: t,
1498 small: n.small,
1499 x: n.x,
1500 y: n.y,
1501 z: n.z,
1502 kids,
1503 fields: &[],
1504 }),
1505 Tag::Fn => {
1506 let (params, ret) = kids.split_at(kids.len().saturating_sub(1));
1507 let ret = ret.first().copied().unwrap_or(TypeId::ERROR);
1508 self.intern(Key {
1509 tag: Tag::Fn,
1510 small: n.small,
1511 x: 0,
1512 y: 0,
1513 z: ret.0,
1514 kids: params,
1515 fields: &[],
1516 })
1517 }
1518 Tag::Record => {
1519 let fields: Vec<Field> = self
1520 .fields_of(&n)
1521 .iter()
1522 .zip(kids)
1523 .map(|(f, &ty)| Field { name: f.name, ty })
1524 .collect();
1525 self.record_sorted(&fields)
1526 }
1527 Tag::Array => self.array_of(first(0), first(1)),
1528 Tag::Nullable => self.nullable(first(0)),
1529 Tag::Map => self.map(first(0), first(1)),
1530 t if t.one_child() => self.simple(t, n.small, first(0).0, 0, 0),
1531 _ => id,
1532 }
1533 }
1534
1535 #[must_use]
1556 pub fn display<'a, L: Lookup>(&'a self, id: TypeId, names: &'a L) -> TypeDisplay<'a, L> {
1557 TypeDisplay {
1558 types: self,
1559 id,
1560 names,
1561 }
1562 }
1563
1564 pub(crate) fn render<L: Lookup>(&self, id: TypeId, names: &L, out: &mut String) {
1565 render(self, id, names, out);
1566 }
1567}
1568
1569fn const_value(n: &Node) -> i64 {
1570 (u64::from(n.x) | (u64::from(n.y) << 32)) as i64
1571}
1572
1573fn foreign_def(n: &Node) -> Option<DefId> {
1574 let unit = UnitId::new(n.x);
1575 let def = if n.small == 0 {
1576 Def::Item(ItemId::from_index(n.y as usize)?)
1577 } else {
1578 Def::Variant(VariantId::from_index(n.y as usize)?)
1579 };
1580 Some(DefId::foreign(unit, def))
1581}
1582
1583pub struct TypeDisplay<'a, L> {
1596 types: &'a Types,
1597 id: TypeId,
1598 names: &'a L,
1599}
1600
1601impl<L: Lookup> fmt::Display for TypeDisplay<'_, L> {
1602 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1603 let mut out = String::new();
1604 render(self.types, self.id, self.names, &mut out);
1605 f.write_str(&out)
1606 }
1607}
1608
1609const RENDER_CAP: usize = 200;
1611
1612enum Piece {
1613 Ty(TypeId),
1614 Text(&'static str),
1615 Name(u32),
1616 Len(u64),
1617 Signed(i64),
1618}
1619
1620fn push_name<L: Lookup>(names: &L, raw: u32, out: &mut String) {
1621 let resolved = Symbol::from_u32(raw).and_then(|s| {
1622 names.resolve_with(s, |text| {
1623 out.push_str(text);
1624 })
1625 });
1626 if resolved.is_none() {
1627 out.push('#');
1628 push_u64(u64::from(raw), out);
1629 }
1630}
1631
1632fn push_u64(mut v: u64, out: &mut String) {
1633 let mut digits = [0u8; 20];
1634 let mut i = digits.len();
1635 loop {
1636 i -= 1;
1637 if let Some(d) = digits.get_mut(i) {
1638 *d = b'0' + (v % 10) as u8;
1639 }
1640 v /= 10;
1641 if v == 0 || i == 0 {
1642 break;
1643 }
1644 }
1645 for &d in digits.get(i..).unwrap_or(&[]) {
1646 out.push(char::from(d));
1647 }
1648}
1649
1650fn push_table_name<L: Lookup>(
1652 table: &[u32],
1653 index: u32,
1654 fallback: &str,
1655 names: &L,
1656 out: &mut String,
1657) {
1658 match table.get(index as usize).copied().filter(|&raw| raw != 0) {
1659 Some(raw) => push_name(names, raw, out),
1660 None => {
1661 out.push_str(fallback);
1662 push_u64(u64::from(index), out);
1663 }
1664 }
1665}
1666
1667fn push_seq(stack: &mut Vec<Piece>, items: &[TypeId], sep: &'static str) {
1669 for (i, &k) in items.iter().enumerate().rev() {
1670 stack.push(Piece::Ty(k));
1671 if i > 0 {
1672 stack.push(Piece::Text(sep));
1673 }
1674 }
1675}
1676
1677fn push_args(stack: &mut Vec<Piece>, args: &[TypeId]) {
1679 if !args.is_empty() {
1680 stack.push(Piece::Text(">"));
1681 push_seq(stack, args, ", ");
1682 stack.push(Piece::Text("<"));
1683 }
1684}
1685
1686#[allow(clippy::too_many_lines)]
1687fn render<L: Lookup>(types: &Types, id: TypeId, names: &L, out: &mut String) {
1688 let mut stack = alloc::vec![Piece::Ty(id)];
1689 while let Some(piece) = stack.pop() {
1690 if out.len() > RENDER_CAP {
1691 out.push('…');
1692 return;
1693 }
1694 let id = match piece {
1695 Piece::Text(t) => {
1696 out.push_str(t);
1697 continue;
1698 }
1699 Piece::Name(raw) => {
1700 push_name(names, raw, out);
1701 continue;
1702 }
1703 Piece::Len(len) => {
1704 push_u64(len, out);
1705 continue;
1706 }
1707 Piece::Signed(v) => {
1708 if v < 0 {
1709 out.push('-');
1710 }
1711 push_u64(v.unsigned_abs(), out);
1712 continue;
1713 }
1714 Piece::Ty(id) => id,
1715 };
1716 let n = types.node(id);
1717 let kids = types.kids_of(&n);
1718 match n.tag {
1719 Tag::Error => out.push_str("{error}"),
1720 Tag::Var => out.push_str(match n.small {
1721 1 => "{integer}",
1722 2 => "{float}",
1723 _ => "_",
1724 }),
1725 Tag::Any => out.push_str("any"),
1726 Tag::Never => out.push('!'),
1727 Tag::Null => out.push_str("null"),
1728 Tag::Prim => out.push_str(
1729 PRIMS
1730 .get(usize::from(n.small))
1731 .copied()
1732 .unwrap_or(Prim::Bool)
1733 .name(),
1734 ),
1735 Tag::Tuple => {
1736 stack.push(Piece::Text(")"));
1737 if kids.len() == 1 {
1738 stack.push(Piece::Text(","));
1739 }
1740 push_seq(&mut stack, kids, ", ");
1741 stack.push(Piece::Text("("));
1742 }
1743 Tag::Array => {
1744 stack.push(Piece::Text("]"));
1745 let len = types.node(TypeId(n.y));
1746 if len.tag == Tag::Const {
1747 stack.push(Piece::Len(const_value(&len) as u64));
1748 } else {
1749 stack.push(Piece::Ty(TypeId(n.y)));
1750 }
1751 stack.push(Piece::Text("; "));
1752 stack.push(Piece::Ty(TypeId(n.x)));
1753 stack.push(Piece::Text("["));
1754 }
1755 Tag::Slice => {
1756 stack.push(Piece::Text("]"));
1757 stack.push(Piece::Ty(TypeId(n.x)));
1758 stack.push(Piece::Text("["));
1759 }
1760 Tag::Ref | Tag::Ptr => {
1761 stack.push(Piece::Ty(TypeId(n.x)));
1762 stack.push(Piece::Text(match (n.tag, n.small != 0) {
1763 (Tag::Ref, false) => "&",
1764 (Tag::Ref, true) => "&mut ",
1765 (_, false) => "*const ",
1766 (_, true) => "*mut ",
1767 }));
1768 }
1769 Tag::Fn => {
1770 stack.push(Piece::Ty(TypeId(n.z)));
1771 stack.push(Piece::Text(") -> "));
1772 push_seq(&mut stack, kids, ", ");
1773 stack.push(Piece::Text("fn("));
1774 if n.small & 0b10 != 0 {
1775 stack.push(Piece::Text("async "));
1776 }
1777 }
1778 Tag::Nullable => {
1779 stack.push(Piece::Text("?"));
1780 let inner = TypeId(n.x);
1781 let compound = matches!(types.node(inner).tag, Tag::Union | Tag::Inter | Tag::Fn);
1782 if compound {
1783 stack.push(Piece::Text(")"));
1784 }
1785 stack.push(Piece::Ty(inner));
1786 if compound {
1787 stack.push(Piece::Text("("));
1788 }
1789 }
1790 Tag::Map => {
1791 stack.push(Piece::Text("}"));
1792 stack.push(Piece::Ty(TypeId(n.y)));
1793 stack.push(Piece::Text(": "));
1794 stack.push(Piece::Ty(TypeId(n.x)));
1795 stack.push(Piece::Text("{"));
1796 }
1797 Tag::Record => {
1798 stack.push(Piece::Text(" }"));
1799 let fields = types.fields_of(&n);
1800 for (i, fl) in fields.iter().enumerate().rev() {
1801 stack.push(Piece::Ty(fl.ty));
1802 stack.push(Piece::Text(": "));
1803 stack.push(Piece::Name(fl.name.as_u32()));
1804 if i > 0 {
1805 stack.push(Piece::Text(", "));
1806 }
1807 }
1808 stack.push(Piece::Text("{ "));
1809 }
1810 Tag::Adt => {
1811 push_args(&mut stack, kids);
1812 push_table_name(&types.item_names, n.x, "item#", names, out);
1813 }
1814 Tag::Trait => {
1815 push_args(&mut stack, kids);
1818 push_table_name(&types.item_names, n.x, "item#", names, out);
1819 }
1820 Tag::Param => push_table_name(&types.binder_names, n.x, "param#", names, out),
1821 Tag::ImplParam => {
1822 out.push_str("impl ");
1823 push_table_name(&types.impl_names, n.x, "#", names, out);
1824 }
1825 Tag::Opaque => {
1826 out.push_str("impl ");
1827 push_table_name(&types.impl_names, n.x, "#", names, out);
1828 }
1829 Tag::Foreign => {
1830 push_args(&mut stack, kids);
1831 out.push('u');
1832 push_u64(u64::from(n.x), out);
1833 out.push_str(if n.small == 0 { ":item#" } else { ":variant#" });
1834 push_u64(u64::from(n.y), out);
1835 }
1836 Tag::Extern => {
1837 push_args(&mut stack, kids);
1838 push_name(names, n.x, out);
1839 }
1840 Tag::SelfOf => out.push_str("Self"),
1841 Tag::Union => push_seq(&mut stack, kids, " | "),
1842 Tag::Inter => push_seq(&mut stack, kids, " & "),
1843 Tag::Dyn => {
1844 push_seq(&mut stack, kids, " + ");
1845 stack.push(Piece::Text("dyn "));
1846 }
1847 Tag::Proj => {
1848 stack.push(Piece::Name(
1850 types.item_names.get(n.y as usize).copied().unwrap_or(0),
1851 ));
1852 stack.push(Piece::Text(">::"));
1853 push_args(&mut stack, kids.get(1..).unwrap_or(&[]));
1854 stack.push(Piece::Name(
1855 types.item_names.get(n.x as usize).copied().unwrap_or(0),
1856 ));
1857 stack.push(Piece::Text(" as "));
1858 stack.push(Piece::Ty(kids.first().copied().unwrap_or(TypeId::ERROR)));
1859 stack.push(Piece::Text("<"));
1860 }
1861 Tag::Const => stack.push(Piece::Signed(const_value(&n))),
1862 Tag::Async | Tag::Task | Tag::Gen | Tag::AsyncGen => {
1863 stack.push(Piece::Text(">"));
1864 stack.push(Piece::Ty(TypeId(n.x)));
1865 stack.push(Piece::Text(match n.tag {
1866 Tag::Async => "async<",
1867 Tag::Task => "task<",
1868 Tag::Gen => "generator<",
1869 _ => "async-generator<",
1870 }));
1871 }
1872 }
1873 }
1874}
1875
1876#[cfg(test)]
1877mod tests {
1878 use alloc::string::ToString;
1879
1880 use hir_lang::{BinderId, Def, DefId, Effects, ItemId, Prim, UnitId, VariantId};
1881 use intern_lang::Interner;
1882
1883 use super::*;
1884
1885 fn item(i: usize) -> ItemId {
1886 ItemId::from_index(i).unwrap_or_else(|| item(0))
1887 }
1888
1889 #[test]
1890 fn test_fixed_ids_are_the_builtins() {
1891 let t = Types::new();
1892 assert_eq!(t.get(TypeId::ERROR), Type::Error);
1893 assert_eq!(t.get(TypeId::ANY), Type::Any);
1894 assert_eq!(t.get(TypeId::NEVER), Type::Never);
1895 assert_eq!(t.get(TypeId::NULL), Type::Null);
1896 assert_eq!(t.get(TypeId::UNIT), Type::Tuple(&[]));
1897 for p in PRIMS {
1898 assert_eq!(t.get(TypeId::prim(p)), Type::Prim(p));
1899 }
1900 assert_eq!(t.len(), 20);
1901 }
1902
1903 #[test]
1904 fn test_hash_consing_survives_table_growth() {
1905 let mut t = Types::new();
1906 let mut ids = alloc::vec::Vec::new();
1907 let mut cur = TypeId::UNIT;
1908 for _ in 0..5_000 {
1909 cur = t.slice(cur);
1910 ids.push(cur);
1911 }
1912 let mut again = TypeId::UNIT;
1914 for &id in &ids {
1915 again = t.slice(again);
1916 assert_eq!(again, id);
1917 }
1918 assert_eq!(t.len(), 20 + 5_000);
1919 }
1920
1921 #[test]
1922 fn test_distinct_shapes_are_distinct() {
1923 let mut t = Types::new();
1924 let i32_ = TypeId::prim(Prim::I32);
1925 let a = t.array(i32_, 3);
1926 let b = t.array(i32_, 4);
1927 let c = t.array(i32_, 3 + (1 << 32));
1928 assert_ne!(a, b);
1929 assert_ne!(a, c);
1930 assert_eq!(
1931 t.get(c),
1932 Type::Array {
1933 elem: i32_,
1934 len: 3 + (1 << 32)
1935 }
1936 );
1937 let r = t.reference(false, i32_);
1938 let m = t.reference(true, i32_);
1939 let p = t.pointer(false, i32_);
1940 assert_ne!(r, m);
1941 assert_ne!(r, p);
1942 let f = t.func(&[i32_], i32_, Effects::NONE);
1943 let g = t.func(&[i32_], i32_, Effects::ASYNC);
1944 assert_ne!(f, g);
1945 assert_eq!(
1946 t.get(g),
1947 Type::Fn {
1948 params: &[i32_],
1949 ret: i32_,
1950 effects: Effects::ASYNC
1951 }
1952 );
1953 let empty_record = t.record(&[]);
1954 assert_ne!(empty_record, TypeId::UNIT);
1955 assert_eq!(t.get(empty_record), Type::Record(&[]));
1956 }
1957
1958 #[test]
1959 fn test_effect_bits_round_trip() {
1960 for e in [
1961 Effects::NONE,
1962 Effects::THROWS,
1963 Effects::ASYNC.union(Effects::YIELD),
1964 Effects::UNSAFE,
1965 ] {
1966 assert_eq!(effects_from_bits(effects_bits(e)), e);
1967 }
1968 }
1969
1970 #[test]
1971 fn test_nominal_and_host_types() {
1972 let mut t = Types::new();
1973 let it = item(7);
1974 let a = t.adt(it);
1975 assert_eq!(
1976 t.get(a),
1977 Type::Adt {
1978 item: it,
1979 args: &[]
1980 }
1981 );
1982 assert_eq!(a, t.adt(it));
1983 let def = DefId::foreign(UnitId::new(3), Def::Item(it));
1984 let f = t.foreign(def);
1985 assert_eq!(t.get(f), Type::Foreign { def, args: &[] });
1986 let v = VariantId::from_index(2)
1987 .map(Def::Variant)
1988 .unwrap_or(Def::Item(it));
1989 let fv = t.foreign(DefId::foreign(UnitId::new(3), v));
1990 assert_ne!(f, fv);
1991 if let Some(b) = BinderId::from_index(1) {
1992 let p = t.param(b);
1993 assert_eq!(t.get(p), Type::Param(b));
1994 }
1995 let s = t.self_of(it);
1996 assert_eq!(t.get(s), Type::SelfOf(it));
1997 let g = t.generator(TypeId::UNIT, true);
1998 assert_eq!(
1999 t.get(g),
2000 Type::Generator {
2001 item: TypeId::UNIT,
2002 is_async: true
2003 }
2004 );
2005 }
2006
2007 #[test]
2008 fn test_rendering_covers_every_form() {
2009 let mut names = Interner::new();
2010 let x = names.intern("x");
2011 let vec = names.intern("Vec");
2012 let mut t = Types::new();
2013 let i32_ = TypeId::prim(Prim::I32);
2014 let cases: alloc::vec::Vec<(TypeId, &str)> = alloc::vec![
2015 (TypeId::ERROR, "{error}"),
2016 (TypeId::ANY, "any"),
2017 (TypeId::NEVER, "!"),
2018 (TypeId::NULL, "null"),
2019 (TypeId::UNIT, "()"),
2020 (t.tuple(&[i32_]), "(i32,)"),
2021 (t.tuple(&[i32_, i32_]), "(i32, i32)"),
2022 (t.array(i32_, 4), "[i32; 4]"),
2023 (t.slice(i32_), "[i32]"),
2024 (t.reference(false, i32_), "&i32"),
2025 (t.reference(true, i32_), "&mut i32"),
2026 (t.pointer(false, i32_), "*const i32"),
2027 (t.pointer(true, i32_), "*mut i32"),
2028 (
2029 t.func(&[i32_], TypeId::UNIT, Effects::ASYNC),
2030 "async fn(i32) -> ()"
2031 ),
2032 (t.nullable(i32_), "i32?"),
2033 (t.map(i32_, i32_), "{i32: i32}"),
2034 (t.record(&[Field { name: x, ty: i32_ }]), "{ x: i32 }"),
2035 (t.external(vec), "Vec"),
2036 (t.external_with(vec, &[i32_]), "Vec<i32>"),
2037 (t.awaitable(i32_), "async<i32>"),
2038 (t.task(i32_), "task<i32>"),
2039 (t.generator(i32_, false), "generator<i32>"),
2040 ];
2041 for (id, want) in cases {
2042 assert_eq!(t.display(id, &names).to_string(), want);
2043 }
2044 let it = item(4);
2045 let adt = t.adt(it);
2046 assert_eq!(t.display(adt, &names).to_string(), "item#4");
2047 t.name_item(it, x);
2048 assert_eq!(t.display(adt, &names).to_string(), "x");
2049 let args = t.adt_with(it, &[i32_, TypeId::UNIT]);
2050 assert_eq!(t.display(args, &names).to_string(), "x<i32, ()>");
2051 let u = t.union(&[i32_, TypeId::prim(Prim::Str)]);
2052 assert_eq!(t.display(u, &names).to_string(), "i32 | str");
2053 let nu = t.nullable(u);
2054 assert_eq!(t.display(nu, &names).to_string(), "(i32 | str)?");
2055 let k = t.constant(-4);
2056 assert_eq!(t.display(k, &names).to_string(), "-4");
2057 }
2058
2059 #[test]
2060 fn test_union_canonical_form() {
2061 let mut t = Types::new();
2062 let (a, b, c) = (
2063 TypeId::prim(Prim::I32),
2064 TypeId::prim(Prim::Str),
2065 TypeId::prim(Prim::Bool),
2066 );
2067 let ab = t.union(&[b, a]);
2068 let abc = t.union(&[ab, c]);
2069 assert_eq!(abc, t.union(&[c, b, a, a]));
2070 assert_eq!(t.union(&[a]), a);
2071 assert_eq!(t.union(&[]), TypeId::NEVER);
2072 assert_eq!(t.union(&[TypeId::NEVER, a]), a);
2073 assert_eq!(t.union(&[a, TypeId::ANY]), TypeId::ANY);
2074 let na = t.nullable(a);
2075 let n = t.union(&[na, b]);
2076 let ab2 = t.union(&[a, b]);
2077 assert_eq!(t.get(n), Type::Nullable(ab2));
2078 assert_eq!(t.union(&[TypeId::NULL]), TypeId::NULL);
2079 let i1 = t.intersection(&[a, b]);
2080 let i2 = t.intersection(&[i1, c]);
2081 assert_eq!(i2, t.intersection(&[c, b, a]));
2082 assert_eq!(t.intersection(&[a, TypeId::NEVER]), TypeId::NEVER);
2083 }
2084
2085 #[test]
2086 fn test_rendering_is_capped() {
2087 let names = Interner::new();
2088 let mut t = Types::new();
2089 let mut cur = TypeId::prim(Prim::I32);
2090 for _ in 0..64 {
2091 cur = t.tuple(&[cur, cur]);
2092 }
2093 let s = t.display(cur, &names).to_string();
2094 assert!(s.ends_with('\u{2026}'));
2095 assert!(s.len() < 300);
2096 }
2097}