use super::error::{Error, ObjectKind};
use super::model::{BitfieldLayout, FieldLayout, Padding, RecordLayout};
use crate::pdb::ir::{Alignment, Database, Field, Record, RecordKind, Type, TypeId};
use std::collections::{BTreeMap, BTreeSet};
#[derive(Clone)]
struct Facts {
size: u64,
alignment: Alignment,
}
struct BitfieldFacts {
storage: TypeId,
position: u8,
length: u8,
end: u64,
object: Facts,
}
struct BitfieldUnit {
offset: u64,
storage: TypeId,
size: u64,
alignment: Alignment,
ranges: Vec<(u64, u64)>,
}
pub(super) struct Engine<'a> {
database: &'a Database,
layouts: BTreeMap<TypeId, RecordLayout>,
visiting: BTreeSet<TypeId>,
}
impl<'a> Engine<'a> {
pub(super) fn new(database: &'a Database) -> Self {
Self {
database,
layouts: BTreeMap::new(),
visiting: BTreeSet::new(),
}
}
pub(super) fn record(mut self, id: TypeId) -> Result<RecordLayout, Error> {
self.layout_record(id)
}
fn facts(&mut self, id: TypeId) -> Result<Facts, Error> {
let ty = self
.database
.types
.get(&id)
.cloned()
.ok_or(Error::MissingType { type_id: id })?;
match ty {
Type::Primitive {
size, alignment, ..
}
| Type::Pointer {
size, alignment, ..
} => {
validate_alignment(id, &alignment)?;
Ok(Facts { size, alignment })
}
Type::Modifier { target, .. } => self.facts(target),
Type::Array { element, size, .. } => {
let element = self.facts(element)?;
if element.size == 0 || size % element.size != 0 {
return Err(Error::MalformedArray {
type_id: id,
size,
element_size: element.size,
});
}
Ok(Facts {
size,
alignment: element.alignment,
})
}
Type::Record(target) => {
let layout = self.layout_record(target)?;
Ok(Facts {
size: layout.size,
alignment: layout.alignment,
})
}
Type::Absent => Err(Error::InvalidObjectType {
type_id: id,
kind: ObjectKind::Absent,
}),
Type::Void => Err(Error::InvalidObjectType {
type_id: id,
kind: ObjectKind::Void,
}),
Type::Procedure(_) => Err(Error::InvalidObjectType {
type_id: id,
kind: ObjectKind::Procedure,
}),
Type::MemberFunction { .. } => Err(Error::InvalidObjectType {
type_id: id,
kind: ObjectKind::MemberFunction,
}),
Type::Bitfield { .. } => Err(Error::BitfieldIndirectUse { type_id: id }),
}
}
fn bitfield_facts(&self, id: TypeId) -> Result<BitfieldFacts, Error> {
let Some(Type::Bitfield {
storage,
position,
length,
}) = self.database.types.get(&id)
else {
return Err(Error::BitfieldIndirectUse { type_id: id });
};
let storage_type =
self.database
.types
.get(storage)
.ok_or(Error::BitfieldStorageMissing {
type_id: id,
storage: *storage,
})?;
let Type::Primitive {
size, alignment, ..
} = storage_type
else {
return Err(Error::BitfieldStorage {
type_id: id,
storage: *storage,
});
};
validate_alignment(*storage, alignment)?;
if *size == 0 {
return Err(Error::BitfieldZeroStorage {
type_id: id,
storage: *storage,
});
}
let storage_bits = size.checked_mul(8).ok_or(Error::BitfieldRange {
type_id: id,
storage: *storage,
position: *position,
length: *length,
storage_size: *size,
})?;
let end =
u64::from(*position)
.checked_add(u64::from(*length))
.ok_or(Error::BitfieldRange {
type_id: id,
storage: *storage,
position: *position,
length: *length,
storage_size: *size,
})?;
if *length == 0 || end > storage_bits {
return Err(Error::BitfieldRange {
type_id: id,
storage: *storage,
position: *position,
length: *length,
storage_size: *size,
});
}
Ok(BitfieldFacts {
storage: *storage,
position: *position,
length: *length,
end,
object: Facts {
size: *size,
alignment: alignment.clone(),
},
})
}
fn layout_record(&mut self, id: TypeId) -> Result<RecordLayout, Error> {
if let Some(layout) = self.layouts.get(&id) {
return Ok(layout.clone());
}
if !self.visiting.insert(id) {
return Err(Error::Cycle { type_id: id });
}
let result = self.layout_record_inner(id);
self.visiting.remove(&id);
let layout = result?;
self.layouts.insert(id, layout.clone());
Ok(layout)
}
fn layout_record_inner(&mut self, id: TypeId) -> Result<RecordLayout, Error> {
let record = self
.database
.record_by_id(id)
.cloned()
.ok_or(Error::MissingRecord { type_id: id })?;
match record.kind {
RecordKind::Union => self.layout_union(&record),
RecordKind::Class | RecordKind::Interface | RecordKind::Struct => {
self.layout_struct(&record)
}
}
}
fn layout_struct(&mut self, record: &Record) -> Result<RecordLayout, Error> {
let mut fields = Vec::with_capacity(record.fields.len());
let mut padding = Vec::new();
let mut previous_offset = None;
let mut extent = 0;
let mut natural_alignment = Some(1);
let mut bitfield_unit = None;
for field in &record.fields {
if previous_offset.is_some_and(|previous| field.offset < previous) {
return Err(Error::FieldsOutOfOrder {
record: record.id,
field: field.name.clone(),
});
}
let bitfield = matches!(
self.database.types.get(&field.ty),
Some(Type::Bitfield { .. })
);
let (facts, metadata) = if bitfield {
let bitfield = self.bitfield_facts(field.ty)?;
self.validate_bitfield_field(record, field, &bitfield, extent, &mut bitfield_unit)?;
(
bitfield.object,
Some(BitfieldLayout {
storage: bitfield.storage,
position: bitfield.position,
length: bitfield.length,
}),
)
} else {
let facts = self.facts(field.ty)?;
if field.offset < extent {
return Err(Error::FieldsOverlap {
record: record.id,
field: field.name.clone(),
});
}
bitfield_unit = None;
(facts, None)
};
let end = field
.offset
.checked_add(facts.size)
.ok_or(Error::Overflow {
type_id: field.ty,
operation: "computing field extent",
})?;
if end > record.size {
return Err(if metadata.is_some() {
Error::BitfieldOutOfBounds {
record: record.id,
field: field.name.clone(),
type_id: field.ty,
storage: metadata.as_ref().map_or(field.ty, |value| value.storage),
}
} else {
Error::FieldOutOfBounds {
record: record.id,
field: field.name.clone(),
}
});
}
if !record.packed
&& let Alignment::Known(alignment) = &facts.alignment
&& field.offset % alignment != 0
{
return Err(Error::MisalignedField {
record: record.id,
field: field.name.clone(),
alignment: *alignment,
});
}
if field.offset > extent {
padding.push(Padding {
offset: extent,
size: field.offset - extent,
});
}
natural_alignment = combine_natural_alignment(natural_alignment, &facts.alignment);
previous_offset = Some(field.offset);
extent = extent.max(end);
fields.push(FieldLayout {
name: field.name.clone(),
ty: field.ty,
offset: field.offset,
size: facts.size,
alignment: facts.alignment,
bitfield: metadata,
});
}
if extent < record.size {
padding.push(Padding {
offset: extent,
size: record.size - extent,
});
}
let natural_alignment = nonempty_natural_alignment(record, natural_alignment);
let alignment = if record.packed {
infer_packed_alignment(record, natural_alignment, &fields)?
} else {
effective_record_alignment(record, natural_alignment)?
};
Ok(RecordLayout {
id: record.id,
kind: record.kind,
size: record.size,
alignment,
packed: record.packed,
natural_alignment,
fields,
padding,
})
}
fn validate_bitfield_field(
&self,
record: &Record,
field: &Field,
bitfield: &BitfieldFacts,
extent: u64,
unit: &mut Option<BitfieldUnit>,
) -> Result<(), Error> {
if field.offset < extent {
let Some(prior) = unit.as_mut().filter(|prior| prior.offset == field.offset) else {
return Err(Error::BitfieldPhysicalOverlap {
record: record.id,
field: field.name.clone(),
storage: bitfield.storage,
});
};
if prior.size != bitfield.object.size || prior.alignment != bitfield.object.alignment {
return Err(Error::BitfieldStorageConflict {
record: record.id,
field: field.name.clone(),
storage: bitfield.storage,
prior_storage: prior.storage,
});
}
if prior
.ranges
.iter()
.any(|&(start, end)| u64::from(bitfield.position) < end && start < bitfield.end)
{
return Err(Error::BitfieldRangeOverlap {
record: record.id,
field: field.name.clone(),
storage: bitfield.storage,
});
}
prior
.ranges
.push((u64::from(bitfield.position), bitfield.end));
} else {
*unit = Some(BitfieldUnit {
offset: field.offset,
storage: bitfield.storage,
size: bitfield.object.size,
alignment: bitfield.object.alignment.clone(),
ranges: vec![(u64::from(bitfield.position), bitfield.end)],
});
}
Ok(())
}
fn layout_union(&mut self, record: &Record) -> Result<RecordLayout, Error> {
let mut fields = Vec::with_capacity(record.fields.len());
let mut extent = 0;
let mut natural_alignment = Some(1);
for field in &record.fields {
if field.offset != 0 {
return Err(Error::UnionFieldOffset {
record: record.id,
field: field.name.clone(),
offset: field.offset,
});
}
let bitfield = matches!(
self.database.types.get(&field.ty),
Some(Type::Bitfield { .. })
);
let (facts, metadata) = if bitfield {
let bitfield = self.bitfield_facts(field.ty)?;
(
bitfield.object,
Some(BitfieldLayout {
storage: bitfield.storage,
position: bitfield.position,
length: bitfield.length,
}),
)
} else {
(self.facts(field.ty)?, None)
};
if facts.size > record.size {
return Err(if let Some(bitfield) = metadata.as_ref() {
Error::BitfieldOutOfBounds {
record: record.id,
field: field.name.clone(),
type_id: field.ty,
storage: bitfield.storage,
}
} else {
Error::FieldOutOfBounds {
record: record.id,
field: field.name.clone(),
}
});
}
natural_alignment = combine_natural_alignment(natural_alignment, &facts.alignment);
extent = extent.max(facts.size);
fields.push(FieldLayout {
name: field.name.clone(),
ty: field.ty,
offset: 0,
size: facts.size,
alignment: facts.alignment,
bitfield: metadata,
});
}
let padding = (extent < record.size)
.then_some(Padding {
offset: extent,
size: record.size - extent,
})
.into_iter()
.collect();
let natural_alignment = nonempty_natural_alignment(record, natural_alignment);
let alignment = if record.packed {
infer_packed_alignment(record, natural_alignment, &fields)?
} else {
effective_record_alignment(record, natural_alignment)?
};
Ok(RecordLayout {
id: record.id,
kind: record.kind,
size: record.size,
alignment,
packed: record.packed,
natural_alignment,
fields,
padding,
})
}
}
fn validate_alignment(id: TypeId, alignment: &Alignment) -> Result<(), Error> {
if let Alignment::Known(alignment) = alignment
&& !alignment.is_power_of_two()
{
return Err(Error::InvalidAlignment {
type_id: id,
alignment: *alignment,
});
}
Ok(())
}
fn effective_record_alignment(
record: &Record,
natural_alignment: Option<u64>,
) -> Result<Alignment, Error> {
let alignment = match record.alignment {
Alignment::Known(alignment) => alignment,
Alignment::Unavailable => match natural_alignment {
Some(alignment) => alignment,
None => return Ok(Alignment::Unavailable),
},
};
validate_alignment(record.id, &Alignment::Known(alignment))?;
if record.size.checked_rem(alignment) != Some(0) {
return Err(Error::RecordSizeAlignment {
record: record.id,
size: record.size,
alignment,
});
}
if matches!(record.alignment, Alignment::Known(_))
&& let Some(natural_alignment) = natural_alignment
&& alignment < natural_alignment
{
return Err(Error::RecordAlignmentTooSmall {
record: record.id,
alignment,
natural_alignment,
});
}
Ok(Alignment::Known(alignment))
}
fn infer_packed_alignment(
record: &Record,
natural_alignment: Option<u64>,
fields: &[FieldLayout],
) -> Result<Alignment, Error> {
if fields.is_empty() {
return match record.alignment {
Alignment::Known(alignment) => {
validate_alignment(record.id, &Alignment::Known(alignment))?;
if ![1, 2, 4, 8, 16].contains(&alignment) {
return Err(Error::PackedLayoutMismatch {
record: record.id,
size: record.size,
});
}
if record.size.checked_rem(alignment) != Some(0) {
return Err(Error::RecordSizeAlignment {
record: record.id,
size: record.size,
alignment,
});
}
Ok(Alignment::Known(alignment))
}
Alignment::Unavailable => Ok(Alignment::Unavailable),
};
}
let Some(natural_alignment) = natural_alignment else {
return Err(Error::PackedAlignmentUnavailable { record: record.id });
};
if let Alignment::Known(alignment) = record.alignment {
validate_alignment(record.id, &Alignment::Known(alignment))?;
}
let mut alignments = BTreeSet::new();
for pack in [1, 2, 4, 8, 16] {
let effective = natural_alignment.min(pack);
if matches!(record.alignment, Alignment::Known(alignment) if alignment != effective) {
continue;
}
if packed_candidate_matches(record, fields, pack, effective)? {
alignments.insert(effective);
}
}
match alignments.len() {
0 => Err(Error::PackedLayoutMismatch {
record: record.id,
size: record.size,
}),
1 => Ok(Alignment::Known(
*alignments.first().expect("one alignment"),
)),
_ => Err(Error::PackedAlignmentAmbiguous {
record: record.id,
alignments: alignments.into_iter().collect(),
}),
}
}
fn packed_candidate_matches(
record: &Record,
fields: &[FieldLayout],
pack: u64,
effective_alignment: u64,
) -> Result<bool, Error> {
let mut extent = 0;
let mut previous_bitfield_unit: Option<(u64, u64, Alignment)> = None;
for field in fields {
let shared_bitfield = field.bitfield.is_some()
&& previous_bitfield_unit
.as_ref()
.is_some_and(|unit| *unit == (field.offset, field.size, field.alignment.clone()));
if shared_bitfield {
continue;
}
let Alignment::Known(alignment) = field.alignment else {
return Err(Error::PackedAlignmentUnavailable { record: record.id });
};
if alignment == 0 || !alignment.is_power_of_two() {
return Err(Error::PackedAlignmentUnavailable { record: record.id });
}
if record.kind != RecordKind::Union
&& round_up(extent, alignment.min(pack), field.ty)? != field.offset
{
return Ok(false);
}
let end = field
.offset
.checked_add(field.size)
.ok_or(Error::Overflow {
type_id: field.ty,
operation: "computing packed field extent",
})?;
extent = extent.max(end);
previous_bitfield_unit = field
.bitfield
.as_ref()
.map(|_| (field.offset, field.size, field.alignment.clone()));
}
if record.kind == RecordKind::Union {
extent = fields.iter().map(|field| field.size).max().unwrap_or(0);
}
Ok(round_up(extent, effective_alignment, record.id)? == record.size)
}
fn round_up(value: u64, alignment: u64, type_id: TypeId) -> Result<u64, Error> {
let addend = alignment.checked_sub(1).ok_or(Error::Overflow {
type_id,
operation: "rounding packed layout",
})?;
value
.checked_add(addend)
.map(|value| value & !addend)
.ok_or(Error::Overflow {
type_id,
operation: "rounding packed layout",
})
}
fn combine_natural_alignment(current: Option<u64>, alignment: &Alignment) -> Option<u64> {
match (current, alignment) {
(Some(current), Alignment::Known(alignment)) => Some(current.max(*alignment)),
(None, Alignment::Known(_)) | (_, Alignment::Unavailable) => None,
}
}
fn nonempty_natural_alignment(record: &Record, alignment: Option<u64>) -> Option<u64> {
(!record.fields.is_empty()).then_some(alignment).flatten()
}