1use crate::{EnumDef, Type, TypeInternPool, TypeKind};
11
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub struct NicheRange {
20 pub offset: u32,
22 pub width: u8,
24 pub start: u128,
26 pub end: u128,
28}
29
30impl NicheRange {
31 pub fn count(&self) -> u128 {
33 self.end - self.start + 1
34 }
35
36 pub fn max_for_width(width: u8) -> u128 {
38 if width >= 16 {
39 u128::MAX
40 } else {
41 (1u128 << (width as u32 * 8)) - 1
42 }
43 }
44}
45
46#[derive(Debug, Clone, Copy, PartialEq, Eq)]
52pub enum DiscriminantStrategy {
53 Separate {
59 tag_offset: u32,
61 tag_width: u8,
63 payload_offset: u32,
65 },
66 Niche {
72 unit_variant: u32,
74 data_variant: u32,
76 niche_offset: u32,
78 niche_width: u8,
80 niche_value: u128,
82 },
83}
84
85#[derive(Debug, Clone, PartialEq, Eq)]
91pub struct Layout {
92 pub size: u64,
94 pub align: u64,
96 pub niches: Vec<NicheRange>,
98 pub discriminant: Option<DiscriminantStrategy>,
100}
101
102impl Layout {
103 pub fn scalar(size: u64, align: u64) -> Self {
105 Self {
106 size,
107 align,
108 niches: Vec::new(),
109 discriminant: None,
110 }
111 }
112
113 pub fn zero_sized() -> Self {
115 Self {
116 size: 0,
117 align: 1,
118 niches: Vec::new(),
119 discriminant: None,
120 }
121 }
122
123 pub fn discriminant_strategy(&self) -> Option<DiscriminantStrategy> {
125 self.discriminant
126 }
127}
128
129pub fn layout_of(pool: &TypeInternPool, ty: Type) -> Layout {
131 if let Some(cached) = pool.cached_layout(ty) {
132 return cached;
133 }
134 let computed = compute_layout(pool, ty);
135 pool.cache_layout(ty, computed.clone());
136 computed
137}
138
139fn compute_layout(pool: &TypeInternPool, ty: Type) -> Layout {
140 match ty.kind() {
141 TypeKind::Bool => Layout {
142 size: 1,
143 align: 1,
144 niches: vec![NicheRange {
147 offset: 0,
148 width: 1,
149 start: 2,
150 end: 255,
151 }],
152 discriminant: None,
153 },
154 TypeKind::I8 | TypeKind::U8 => Layout::scalar(1, 1),
155 TypeKind::I16 | TypeKind::U16 | TypeKind::F16 => Layout::scalar(2, 2),
156 TypeKind::I32 | TypeKind::U32 | TypeKind::F32 => Layout::scalar(4, 4),
157 TypeKind::I64 | TypeKind::U64 | TypeKind::F64 => Layout::scalar(8, 8),
158 TypeKind::Char => Layout {
163 size: 4,
164 align: 4,
165 niches: vec![
166 NicheRange {
167 offset: 0,
168 width: 4,
169 start: 0xD800,
170 end: 0xDFFF,
171 },
172 NicheRange {
173 offset: 0,
174 width: 4,
175 start: 0x110000,
176 end: 0xFFFFFFFF,
177 },
178 ],
179 discriminant: None,
180 },
181 TypeKind::Isize | TypeKind::Usize => Layout::scalar(8, 8),
183 TypeKind::CSchar | TypeKind::CUchar => Layout::scalar(1, 1),
186 TypeKind::CShort | TypeKind::CUshort => Layout::scalar(2, 2),
187 TypeKind::CInt | TypeKind::CUint => Layout::scalar(4, 4),
188 TypeKind::CLong | TypeKind::CUlong | TypeKind::CLonglong | TypeKind::CUlonglong => {
189 Layout::scalar(8, 8)
190 }
191 TypeKind::CFloat => Layout::scalar(4, 4),
192 TypeKind::CDouble => Layout::scalar(8, 8),
193 TypeKind::CVoid => Layout::zero_sized(),
197 TypeKind::PtrConst(_) | TypeKind::PtrMut(_) => Layout::scalar(8, 8),
198 TypeKind::Ref(_) | TypeKind::MutRef(_) => Layout::scalar(8, 8),
199 TypeKind::Slice(_) | TypeKind::MutSlice(_) => Layout::scalar(16, 8),
201 TypeKind::Vec(_) => Layout::scalar(24, 8),
203 TypeKind::Interface(_) => Layout::scalar(16, 8),
205
206 TypeKind::Struct(id) => {
207 let def = pool.struct_def(id);
208 let mut offset = 0u64;
209 let mut max_align = 1u64;
210 let mut niches = Vec::new();
211 for f in &def.fields {
212 let field_layout = layout_of(pool, f.ty);
213 if field_layout.size == 0 {
214 continue;
215 }
216 max_align = max_align.max(field_layout.align);
217 offset = align_up(offset, field_layout.align);
218 for n in &field_layout.niches {
221 niches.push(NicheRange {
222 offset: n.offset + offset as u32,
223 width: n.width,
224 start: n.start,
225 end: n.end,
226 });
227 }
228 offset += field_layout.size;
229 }
230 if max_align > 1 {
231 offset = align_up(offset, max_align);
232 }
233 Layout {
234 size: offset,
235 align: max_align,
236 niches,
237 discriminant: None,
238 }
239 }
240
241 TypeKind::Array(id) => {
242 let (elem_ty, len) = pool.array_def(id);
243 let elem = layout_of(pool, elem_ty);
244 Layout {
245 size: elem.size * len,
246 align: elem.align,
247 niches: Vec::new(),
248 discriminant: None,
249 }
250 }
251
252 TypeKind::Enum(id) => {
253 let def = pool.enum_def(id);
254 if let Some(niche_layout) = try_niche_encoded_enum_layout(pool, &def) {
255 return niche_layout;
256 }
257 enum_layout_separate(pool, &def)
258 }
259
260 TypeKind::Unit
262 | TypeKind::Never
263 | TypeKind::Error
264 | TypeKind::ComptimeType
265 | TypeKind::ComptimeStr
266 | TypeKind::ComptimeInt
267 | TypeKind::Module(_) => Layout::zero_sized(),
268 }
269}
270
271fn enum_layout_separate(pool: &TypeInternPool, def: &EnumDef) -> Layout {
276 let discrim_layout = layout_of(pool, def.discriminant_type());
277 let tag_width = discrim_layout.size as u8;
278 if def.is_unit_only() {
279 let strategy = DiscriminantStrategy::Separate {
283 tag_offset: 0,
284 tag_width,
285 payload_offset: discrim_layout.size as u32,
286 };
287 let variant_count = def.variants.len() as u128;
288 let max = NicheRange::max_for_width(tag_width);
289 let niches = if variant_count > 0 && variant_count <= max {
290 vec![NicheRange {
291 offset: 0,
292 width: tag_width,
293 start: variant_count,
294 end: max,
295 }]
296 } else {
297 Vec::new()
298 };
299 return Layout {
300 size: discrim_layout.size,
301 align: discrim_layout.align,
302 niches,
303 discriminant: Some(strategy),
304 };
305 }
306
307 if def.is_c_layout {
314 let max_variant_align: u64 = def
315 .variants
316 .iter()
317 .flat_map(|v| v.fields.iter())
318 .map(|f| layout_of(pool, *f).align)
319 .max()
320 .unwrap_or(1);
321 let enum_align = discrim_layout.align.max(max_variant_align);
322 let payload_offset = align_up(discrim_layout.size, enum_align);
323 let max_payload: u64 = def
324 .variants
325 .iter()
326 .map(|v| {
327 v.fields
328 .iter()
329 .map(|f| layout_of(pool, *f).size)
330 .sum::<u64>()
331 })
332 .max()
333 .unwrap_or(0);
334 let strategy = DiscriminantStrategy::Separate {
335 tag_offset: 0,
336 tag_width,
337 payload_offset: payload_offset as u32,
338 };
339 let total_payload = align_up(max_payload, enum_align);
340 let size = align_up(payload_offset + total_payload, enum_align);
341 return Layout {
342 size,
343 align: enum_align,
344 niches: Vec::new(),
345 discriminant: Some(strategy),
346 };
347 }
348
349 let strategy = DiscriminantStrategy::Separate {
351 tag_offset: 0,
352 tag_width,
353 payload_offset: discrim_layout.size as u32,
354 };
355 let max_payload: u64 = def
356 .variants
357 .iter()
358 .map(|v| {
359 v.fields
360 .iter()
361 .map(|f| layout_of(pool, *f).size)
362 .sum::<u64>()
363 })
364 .max()
365 .unwrap_or(0);
366 if max_payload == 0 {
367 return Layout {
368 size: discrim_layout.size,
369 align: discrim_layout.align,
370 niches: Vec::new(),
371 discriminant: Some(strategy),
372 };
373 }
374 let total = discrim_layout.size + max_payload;
375 let size = align_up(total, discrim_layout.align);
376 Layout {
377 size,
378 align: discrim_layout.align,
379 niches: Vec::new(),
380 discriminant: Some(strategy),
381 }
382}
383
384fn try_niche_encoded_enum_layout(pool: &TypeInternPool, def: &EnumDef) -> Option<Layout> {
393 if def.variants.len() != 2 {
394 return None;
395 }
396 let (unit_idx, data_idx) = match (def.variants[0].has_data(), def.variants[1].has_data()) {
397 (false, true) => (0u32, 1u32),
398 (true, false) => (1u32, 0u32),
399 _ => return None,
400 };
401 let data_variant = &def.variants[data_idx as usize];
402 if data_variant.fields.len() != 1 {
403 return None;
405 }
406 let payload_ty = data_variant.fields[0];
407 let payload_layout = layout_of(pool, payload_ty);
408 let niche = payload_layout.niches.first()?;
409 let niche_value = niche.start;
412 let remaining_start = niche.start + 1;
413 let mut composed_niches = Vec::new();
414 if remaining_start <= niche.end {
415 composed_niches.push(NicheRange {
416 offset: niche.offset,
417 width: niche.width,
418 start: remaining_start,
419 end: niche.end,
420 });
421 }
422 Some(Layout {
423 size: payload_layout.size,
424 align: payload_layout.align,
425 niches: composed_niches,
426 discriminant: Some(DiscriminantStrategy::Niche {
427 unit_variant: unit_idx,
428 data_variant: data_idx,
429 niche_offset: niche.offset,
430 niche_width: niche.width,
431 niche_value,
432 }),
433 })
434}
435
436#[inline]
437fn align_up(value: u64, align: u64) -> u64 {
438 debug_assert!(align.is_power_of_two());
439 (value + align - 1) & !(align - 1)
440}
441
442#[cfg(test)]
443mod tests {
444 use super::*;
445 use crate::{EnumVariantDef, StructDef, StructField};
446 use gruel_builtins::Posture;
447 use gruel_util::FileId;
448 use lasso::Rodeo;
449
450 fn fresh_pool() -> TypeInternPool {
451 TypeInternPool::new()
452 }
453
454 #[test]
455 fn bool_has_niche_2_through_255() {
456 let p = fresh_pool();
457 let layout = layout_of(&p, Type::BOOL);
458 assert_eq!(layout.size, 1);
459 assert_eq!(layout.align, 1);
460 assert_eq!(
461 layout.niches,
462 vec![NicheRange {
463 offset: 0,
464 width: 1,
465 start: 2,
466 end: 255,
467 }]
468 );
469 }
470
471 #[test]
472 fn unit_enum_exposes_unused_discriminant_as_niche() {
473 let p = fresh_pool();
474 let mut rodeo = Rodeo::default();
475 let name = rodeo.get_or_intern("E3");
476 let def = crate::EnumDef {
477 name: "E3".into(),
478 variants: vec![
479 EnumVariantDef::unit("A"),
480 EnumVariantDef::unit("B"),
481 EnumVariantDef::unit("C"),
482 ],
483 posture: Posture::Affine,
484 thread_safety: gruel_builtins::ThreadSafety::Sync,
485 is_pub: false,
486 file_id: FileId::DEFAULT,
487 destructor: None,
488 is_c_layout: false,
489 };
490 let (eid, _) = p.register_enum(name, def);
491 let layout = layout_of(&p, Type::new_enum(eid));
492 assert_eq!(layout.size, 1);
493 assert_eq!(
494 layout.niches,
495 vec![NicheRange {
496 offset: 0,
497 width: 1,
498 start: 3,
499 end: 255,
500 }]
501 );
502 }
503
504 #[test]
505 fn primitive_sizes() {
506 let p = fresh_pool();
507 assert_eq!(layout_of(&p, Type::I8), Layout::scalar(1, 1));
508 assert_eq!(layout_of(&p, Type::I16), Layout::scalar(2, 2));
509 assert_eq!(layout_of(&p, Type::I32), Layout::scalar(4, 4));
510 assert_eq!(layout_of(&p, Type::I64), Layout::scalar(8, 8));
511 assert_eq!(layout_of(&p, Type::U8), Layout::scalar(1, 1));
512 assert_eq!(layout_of(&p, Type::U16), Layout::scalar(2, 2));
513 assert_eq!(layout_of(&p, Type::U32), Layout::scalar(4, 4));
514 assert_eq!(layout_of(&p, Type::U64), Layout::scalar(8, 8));
515 assert_eq!(layout_of(&p, Type::ISIZE), Layout::scalar(8, 8));
516 assert_eq!(layout_of(&p, Type::USIZE), Layout::scalar(8, 8));
517 assert_eq!(layout_of(&p, Type::F16), Layout::scalar(2, 2));
518 assert_eq!(layout_of(&p, Type::F32), Layout::scalar(4, 4));
519 assert_eq!(layout_of(&p, Type::F64), Layout::scalar(8, 8));
520 let bool_layout = layout_of(&p, Type::BOOL);
522 assert_eq!(bool_layout.size, 1);
523 assert_eq!(bool_layout.align, 1);
524 }
525
526 #[test]
527 fn unit_and_never_are_zero_sized() {
528 let p = fresh_pool();
529 assert_eq!(layout_of(&p, Type::UNIT).size, 0);
530 assert_eq!(layout_of(&p, Type::NEVER).size, 0);
531 }
532
533 #[test]
534 fn struct_layout_packs_with_padding() {
535 let p = fresh_pool();
536 let mut rodeo = Rodeo::default();
537 let name = rodeo.get_or_intern("S");
538 let def = StructDef {
539 name: "S".into(),
540 fields: vec![
541 StructField {
542 name: "a".into(),
543 ty: Type::U8,
544
545 is_pub: true,
546 },
547 StructField {
548 name: "b".into(),
549 ty: Type::U32,
550
551 is_pub: true,
552 },
553 StructField {
554 name: "c".into(),
555 ty: Type::U8,
556
557 is_pub: true,
558 },
559 ],
560 posture: Posture::Affine,
561 is_clone: false,
562 thread_safety: gruel_builtins::ThreadSafety::Sync,
563 destructor: None,
564 is_builtin: false,
565 is_pub: false,
566 file_id: FileId::DEFAULT,
567 is_c_layout: false,
568 };
569 let (sid, _) = p.register_struct(name, def);
570 let ty = Type::new_struct(sid);
571 let layout = layout_of(&p, ty);
572 assert_eq!(layout.size, 12);
574 assert_eq!(layout.align, 4);
575 assert!(layout.niches.is_empty());
576 }
577
578 fn make_option_bool(p: &TypeInternPool, name: &str) -> Type {
579 let mut rodeo = Rodeo::default();
580 let s = rodeo.get_or_intern(name);
581 let mut some = EnumVariantDef::unit("Some");
582 some.fields = vec![Type::BOOL];
583 let def = crate::EnumDef {
584 name: name.to_string(),
585 variants: vec![EnumVariantDef::unit("None"), some],
586 posture: Posture::Affine,
587 thread_safety: gruel_builtins::ThreadSafety::Sync,
588 is_pub: false,
589 file_id: FileId::DEFAULT,
590 destructor: None,
591 is_c_layout: false,
592 };
593 let (eid, _) = p.register_enum(s, def);
594 Type::new_enum(eid)
595 }
596
597 #[test]
598 fn option_bool_collapses_to_one_byte() {
599 let p = fresh_pool();
600 let ty = make_option_bool(&p, "OptB2");
601 let layout = layout_of(&p, ty);
602 assert_eq!(layout.size, 1, "Option(bool) should collapse to 1 byte");
603 assert_eq!(layout.align, 1);
604 match layout.discriminant_strategy().unwrap() {
605 DiscriminantStrategy::Niche {
606 niche_offset,
607 niche_width,
608 niche_value,
609 unit_variant,
610 data_variant,
611 } => {
612 assert_eq!(niche_offset, 0);
613 assert_eq!(niche_width, 1);
614 assert_eq!(niche_value, 2, "first reserved niche value");
615 assert_eq!(unit_variant, 0);
616 assert_eq!(data_variant, 1);
617 }
618 other => panic!("expected Niche, got {other:?}"),
619 }
620 assert_eq!(
622 layout.niches,
623 vec![NicheRange {
624 offset: 0,
625 width: 1,
626 start: 3,
627 end: 255,
628 }]
629 );
630 }
631
632 #[test]
633 fn nested_option_bool_collapses_recursively() {
634 let p = fresh_pool();
635 let inner = make_option_bool(&p, "OptB_inner");
637 let mut rodeo = Rodeo::default();
638 let mid_name = rodeo.get_or_intern("OptOptB");
639 let mut some_mid = EnumVariantDef::unit("Some");
640 some_mid.fields = vec![inner];
641 let mid_def = crate::EnumDef {
642 name: "OptOptB".into(),
643 variants: vec![EnumVariantDef::unit("None"), some_mid],
644 posture: Posture::Affine,
645 thread_safety: gruel_builtins::ThreadSafety::Sync,
646 is_pub: false,
647 file_id: FileId::DEFAULT,
648 destructor: None,
649 is_c_layout: false,
650 };
651 let (mid_eid, _) = p.register_enum(mid_name, mid_def);
652 let mid = Type::new_enum(mid_eid);
653 let outer_name = rodeo.get_or_intern("OptOptOptB");
654 let mut some_outer = EnumVariantDef::unit("Some");
655 some_outer.fields = vec![mid];
656 let outer_def = crate::EnumDef {
657 name: "OptOptOptB".into(),
658 variants: vec![EnumVariantDef::unit("None"), some_outer],
659 posture: Posture::Affine,
660 thread_safety: gruel_builtins::ThreadSafety::Sync,
661 is_pub: false,
662 file_id: FileId::DEFAULT,
663 destructor: None,
664 is_c_layout: false,
665 };
666 let (outer_eid, _) = p.register_enum(outer_name, outer_def);
667 let outer = Type::new_enum(outer_eid);
668 let layout = layout_of(&p, outer);
669 assert_eq!(
670 layout.size, 1,
671 "Option(Option(Option(bool))) should collapse to 1 byte"
672 );
673 }
674
675 #[test]
676 fn struct_inherits_field_niches() {
677 let p = fresh_pool();
678 let mut rodeo = Rodeo::default();
679 let name = rodeo.get_or_intern("Wrap");
680 let def = StructDef {
682 name: "Wrap".into(),
683 fields: vec![
684 StructField {
685 name: "pad".into(),
686 ty: Type::U8,
687
688 is_pub: true,
689 },
690 StructField {
691 name: "b".into(),
692 ty: Type::BOOL,
693
694 is_pub: true,
695 },
696 ],
697 posture: Posture::Affine,
698 is_clone: false,
699 thread_safety: gruel_builtins::ThreadSafety::Sync,
700 destructor: None,
701 is_builtin: false,
702 is_pub: false,
703 file_id: FileId::DEFAULT,
704 is_c_layout: false,
705 };
706 let (sid, _) = p.register_struct(name, def);
707 let layout = layout_of(&p, Type::new_struct(sid));
708 assert_eq!(
710 layout.niches,
711 vec![NicheRange {
712 offset: 1,
713 width: 1,
714 start: 2,
715 end: 255,
716 }]
717 );
718 }
719
720 #[test]
721 fn unit_only_enum_is_discriminant_sized() {
722 let p = fresh_pool();
723 let mut rodeo = Rodeo::default();
724 let name = rodeo.get_or_intern("Color");
725 let def = crate::EnumDef {
726 name: "Color".into(),
727 variants: vec![
728 EnumVariantDef::unit("R"),
729 EnumVariantDef::unit("G"),
730 EnumVariantDef::unit("B"),
731 ],
732 posture: Posture::Affine,
733 thread_safety: gruel_builtins::ThreadSafety::Sync,
734 is_pub: false,
735 file_id: FileId::DEFAULT,
736 destructor: None,
737 is_c_layout: false,
738 };
739 let (eid, _) = p.register_enum(name, def);
740 let ty = Type::new_enum(eid);
741 let layout = layout_of(&p, ty);
742 assert_eq!(layout.size, 1);
743 assert_eq!(layout.align, 1);
744 }
745}