rc::Rc,
};
+use crate::{
+ loc::Loc,
+ loc_set::{LocSet, LocSetMaxConflictsWith},
+};
+
#[derive(Clone)]
pub struct Interned<T: ?Sized> {
ptr: Rc<T>,
#[derive(Default)]
struct Interners {
str: Interner<str>,
+ loc_set: Interner<LocSet>,
+ loc_set_max_conflicts_with_loc_set: Interner<LocSetMaxConflictsWith<Interned<LocSet>>>,
+ loc_set_max_conflicts_with_loc: Interner<LocSetMaxConflictsWith<Loc>>,
}
-pub struct GlobalArena {
+pub struct GlobalState {
interners: Interners,
}
-scoped_tls::scoped_thread_local!(static GLOBAL_ARENA: GlobalArena);
+scoped_tls::scoped_thread_local!(static GLOBAL_STATE: GlobalState);
-impl GlobalArena {
+impl GlobalState {
pub fn scope<R>(f: impl FnOnce() -> R) -> R {
- GLOBAL_ARENA.set(
- &GlobalArena {
+ GLOBAL_STATE.set(
+ &GlobalState {
interners: Interners::default(),
},
f,
)
}
- pub fn get<R>(f: impl for<'a> FnOnce(&'a GlobalArena) -> R) -> R {
- GLOBAL_ARENA.with(f)
+ pub fn get<R>(f: impl for<'a> FnOnce(&'a GlobalState) -> R) -> R {
+ GLOBAL_STATE.with(f)
}
}
}
pub trait InternTarget: Intern<Target = Self> + Hash + Eq {
- fn get_interner(global_arena: &GlobalArena) -> &Interner<Self>;
- fn into_interned(input: Self, global_arena: &GlobalArena) -> Interned<Self>
+ fn get_interner(global_state: &GlobalState) -> &Interner<Self>;
+ fn into_interned(input: Self, global_state: &GlobalState) -> Interned<Self>
where
Self: Sized,
{
- Self::get_interner(global_arena).intern(InternInput {
+ Self::get_interner(global_state).intern(InternInput {
input,
borrow: |v| v,
into_rc: Rc::new,
})
}
- fn rc_into_interned(input: Rc<Self>, global_arena: &GlobalArena) -> Interned<Self> {
- Self::get_interner(global_arena).intern(InternInput {
+ fn rc_into_interned(input: Rc<Self>, global_state: &GlobalState) -> Interned<Self> {
+ Self::get_interner(global_state).intern(InternInput {
input,
borrow: |v| &**v,
into_rc: |v| v,
})
}
- fn rc_to_interned(input: &Rc<Self>, global_arena: &GlobalArena) -> Interned<Self> {
- Self::get_interner(global_arena).intern(InternInput {
+ fn rc_to_interned(input: &Rc<Self>, global_state: &GlobalState) -> Interned<Self> {
+ Self::get_interner(global_state).intern(InternInput {
input,
borrow: |v| &***v,
into_rc: |v| v.clone(),
}
impl InternTarget for str {
- fn get_interner(global_arena: &GlobalArena) -> &Interner<Self> {
- &global_arena.interners.str
+ fn get_interner(global_state: &GlobalState) -> &Interner<Self> {
+ &global_state.interners.str
}
}
v.into()
}
- fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
- Self::get_interner(global_arena).intern(InternInput {
+ fn to_interned(&self, global_state: &GlobalState) -> Interned<Self::Target> {
+ Self::get_interner(global_state).intern(InternInput {
input: self,
borrow: |v| &**v,
into_rc: Self::to_rc_target,
Rc::from(*v)
}
- fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
- Self::Target::to_interned(self, global_arena)
+ fn to_interned(&self, global_state: &GlobalState) -> Interned<Self::Target> {
+ Self::Target::to_interned(self, global_state)
}
- fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
+ fn into_interned(self, global_state: &GlobalState) -> Interned<Self::Target>
where
Self: Sized,
{
- Self::Target::to_interned(self, global_arena)
+ Self::Target::to_interned(self, global_state)
}
}
Rc::from(&**v)
}
- fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
- Self::Target::to_interned(self, global_arena)
+ fn to_interned(&self, global_state: &GlobalState) -> Interned<Self::Target> {
+ Self::Target::to_interned(self, global_state)
}
- fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
+ fn into_interned(self, global_state: &GlobalState) -> Interned<Self::Target>
where
Self: Sized,
{
- Self::Target::to_interned(self, global_arena)
+ Self::Target::to_interned(self, global_state)
}
}
Rc::from(&**v)
}
- fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
- Self::Target::to_interned(self, global_arena)
+ fn to_interned(&self, global_state: &GlobalState) -> Interned<Self::Target> {
+ Self::Target::to_interned(self, global_state)
}
fn into_rc_target(v: Self) -> Rc<Self::Target>
Rc::from(v)
}
- fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
+ fn into_interned(self, global_state: &GlobalState) -> Interned<Self::Target>
where
Self: Sized,
{
- Self::Target::to_interned(&self, global_arena)
+ Self::Target::to_interned(&self, global_state)
}
}
Self::to_rc_target(&v)
}
fn to_rc_target(v: &Self) -> Rc<Self::Target>;
- fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
+ fn into_interned(self, global_state: &GlobalState) -> Interned<Self::Target>
where
Self: Sized,
{
<<Self as Intern>::Target as InternTarget>::rc_into_interned(
Self::into_rc_target(self),
- global_arena,
+ global_state,
)
}
- fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
- Self::Target::rc_into_interned(Self::to_rc_target(self), global_arena)
+ fn to_interned(&self, global_state: &GlobalState) -> Interned<Self::Target> {
+ Self::Target::rc_into_interned(Self::to_rc_target(self), global_state)
}
}
v.into()
}
- fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
+ fn into_interned(self, global_state: &GlobalState) -> Interned<Self::Target>
where
Self: Sized,
{
- InternTarget::into_interned(self, global_arena)
+ InternTarget::into_interned(self, global_state)
}
- fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
- InternTarget::get_interner(global_arena).intern(InternInput {
+ fn to_interned(&self, global_state: &GlobalState) -> Interned<Self::Target> {
+ InternTarget::get_interner(global_state).intern(InternInput {
input: self,
borrow: |v| &**v,
into_rc: |v| v.clone().into(),
})
}
}
+
+impl InternTarget for LocSet {
+ fn get_interner(global_state: &GlobalState) -> &Interner<Self> {
+ &global_state.interners.loc_set
+ }
+}
+
+impl InternTarget for LocSetMaxConflictsWith<Interned<LocSet>> {
+ fn get_interner(global_state: &GlobalState) -> &Interner<Self> {
+ &global_state.interners.loc_set_max_conflicts_with_loc_set
+ }
+}
+
+impl InternTarget for LocSetMaxConflictsWith<Loc> {
+ fn get_interner(global_state: &GlobalState) -> &Interner<Self> {
+ &global_state.interners.loc_set_max_conflicts_with_loc
+ }
+}
+use crate::{
+ error::{Error, Result},
+ interned::{GlobalState, Intern, InternTarget, Interned},
+ loc::{BaseTy, Loc, LocFields, LocKind, Ty, TyFields},
+};
+use enum_map::{enum_map, EnumMap};
+use num_bigint::BigUint;
+use num_traits::Zero;
+use serde::{Deserialize, Serialize};
+use std::{
+ borrow::{Borrow, Cow},
+ cell::Cell,
+ fmt,
+ hash::Hash,
+ iter::{FusedIterator, Peekable},
+ num::NonZeroU32,
+ ops::{
+ BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, ControlFlow, Range, Sub,
+ SubAssign,
+ },
+};
+
+#[derive(Deserialize)]
+struct LocSetSerialized {
+ starts: EnumMap<LocKind, BigUint>,
+ ty: Option<Ty>,
+}
+
+impl TryFrom<LocSetSerialized> for LocSet {
+ type Error = Error;
+
+ fn try_from(value: LocSetSerialized) -> Result<Self, Self::Error> {
+ Self::from_parts(value.starts, value.ty)
+ }
+}
+
+#[derive(Clone, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
+#[serde(try_from = "LocSetSerialized")]
pub struct LocSet {
- // FIXME: finish
+ starts: EnumMap<LocKind, BigUint>,
+ ty: Option<Ty>,
+}
+
+/// computes same value as `a & !b`, but more efficiently
+fn and_not<A: Borrow<BigUint>, B>(a: A, b: B) -> BigUint
+where
+ BigUint: for<'a> BitXor<A, Output = BigUint>,
+ B: for<'a> BitAnd<&'a BigUint, Output = BigUint>,
+{
+ // use logical equivalent that avoids needing to use BigInt
+ (b & a.borrow()) ^ a
+}
+
+impl LocSet {
+ pub fn starts(&self) -> &EnumMap<LocKind, BigUint> {
+ &self.starts
+ }
+ pub fn stops(&self) -> EnumMap<LocKind, BigUint> {
+ let Some(ty) = self.ty else {
+ return EnumMap::default();
+ };
+ enum_map! {kind => &self.starts[kind] << ty.reg_len.get()}
+ }
+ pub fn ty(&self) -> Option<Ty> {
+ self.ty
+ }
+ pub fn kinds(&self) -> impl Iterator<Item = LocKind> + '_ {
+ self.starts
+ .iter()
+ .filter_map(|(kind, starts)| if starts.is_zero() { None } else { Some(kind) })
+ }
+ pub fn reg_len(&self) -> Option<NonZeroU32> {
+ self.ty.map(|v| v.reg_len)
+ }
+ pub fn base_ty(&self) -> Option<BaseTy> {
+ self.ty.map(|v| v.base_ty)
+ }
+ pub fn new() -> Self {
+ Self::default()
+ }
+ pub fn from_parts(starts: EnumMap<LocKind, BigUint>, ty: Option<Ty>) -> Result<Self> {
+ let mut empty = true;
+ for (kind, starts) in &starts {
+ if !starts.is_zero() {
+ empty = false;
+ let expected_ty = Ty::new(TyFields {
+ base_ty: kind.base_ty(),
+ reg_len: ty.map(|v| v.reg_len).unwrap_or(nzu32_lit!(1)),
+ })
+ .unwrap_or_else(|_| {
+ Ty::new(TyFields {
+ base_ty: kind.base_ty(),
+ reg_len: nzu32_lit!(1),
+ })
+ .unwrap()
+ });
+ if ty != Some(expected_ty) {
+ return Err(Error::TyMismatch {
+ ty,
+ expected_ty: Some(expected_ty),
+ });
+ }
+ // bits() is one past max bit set, so use >= rather than >
+ if starts.bits() >= Loc::max_start(kind, expected_ty.reg_len)? as u64 {
+ return Err(Error::StartNotInValidRange);
+ }
+ }
+ }
+ if empty && ty.is_some() {
+ Err(Error::TyMismatch {
+ ty,
+ expected_ty: None,
+ })
+ } else {
+ Ok(Self { starts, ty })
+ }
+ }
+ pub fn clear(&mut self) {
+ for v in self.starts.values_mut() {
+ v.assign_from_slice(&[]);
+ }
+ }
+ pub fn contains(&self, value: Loc) -> bool {
+ Some(value.ty()) == self.ty && self.starts[value.kind].bit(value.start as _)
+ }
+ pub fn try_insert(&mut self, value: Loc) -> Result<bool> {
+ if self.is_empty() {
+ self.ty = Some(value.ty());
+ self.starts[value.kind].set_bit(value.start as u64, true);
+ return Ok(true);
+ };
+ let ty = Some(value.ty());
+ if ty != self.ty {
+ return Err(Error::TyMismatch {
+ ty,
+ expected_ty: self.ty,
+ });
+ }
+ let retval = !self.starts[value.kind].bit(value.start as u64);
+ self.starts[value.kind].set_bit(value.start as u64, true);
+ Ok(retval)
+ }
+ pub fn insert(&mut self, value: Loc) -> bool {
+ self.try_insert(value).unwrap()
+ }
+ pub fn remove(&mut self, value: Loc) -> bool {
+ if self.contains(value) {
+ self.starts[value.kind].set_bit(value.start as u64, false);
+ if self.starts.values().all(BigUint::is_zero) {
+ self.ty = None;
+ }
+ true
+ } else {
+ false
+ }
+ }
+ pub fn is_empty(&self) -> bool {
+ self.ty.is_none()
+ }
+ pub fn is_disjoint(&self, other: &LocSet) -> bool {
+ if self.ty != other.ty || self.is_empty() {
+ return true;
+ }
+ for (k, lhs) in self.starts.iter() {
+ let rhs = &other.starts[k];
+ if !(lhs & rhs).is_zero() {
+ return false;
+ }
+ }
+ true
+ }
+ pub fn is_subset(&self, containing_set: &LocSet) -> bool {
+ if self.is_empty() {
+ return true;
+ }
+ if self.ty != containing_set.ty {
+ return false;
+ }
+ for (k, v) in self.starts.iter() {
+ let containing_set = &containing_set.starts[k];
+ if !and_not(v, containing_set).is_zero() {
+ return false;
+ }
+ }
+ true
+ }
+ pub fn is_superset(&self, contained_set: &LocSet) -> bool {
+ contained_set.is_subset(self)
+ }
+ pub fn iter(&self) -> Iter<'_> {
+ if let Some(ty) = self.ty {
+ let mut starts = self.starts.iter().peekable();
+ Iter {
+ internals: Some(IterInternals {
+ ty,
+ start_range: get_start_range(starts.peek()),
+ starts,
+ }),
+ }
+ } else {
+ Iter { internals: None }
+ }
+ }
+ pub fn len(&self) -> usize {
+ let retval: u64 = self.starts.values().map(BigUint::count_ones).sum();
+ retval as usize
+ }
+}
+
+#[derive(Clone, Debug)]
+struct IterInternals<I, T>
+where
+ I: Iterator<Item = (LocKind, T)>,
+ T: Clone + Borrow<BigUint>,
+{
+ ty: Ty,
+ starts: Peekable<I>,
+ start_range: Range<u32>,
+}
+
+impl<I, T> IterInternals<I, T>
+where
+ I: Iterator<Item = (LocKind, T)>,
+ T: Clone + Borrow<BigUint>,
+{
+ fn next(&mut self) -> Option<Loc> {
+ let IterInternals {
+ ty,
+ ref mut starts,
+ ref mut start_range,
+ } = *self;
+ loop {
+ let (kind, ref v) = *starts.peek()?;
+ let Some(start) = start_range.next() else {
+ starts.next();
+ *start_range = get_start_range(starts.peek());
+ continue;
+ };
+ if v.borrow().bit(start as u64) {
+ return Some(
+ Loc::new(LocFields {
+ kind,
+ start,
+ reg_len: ty.reg_len,
+ })
+ .expect("known to be valid"),
+ );
+ }
+ }
+ }
+}
+
+fn get_start_range(v: Option<&(LocKind, impl Borrow<BigUint>)>) -> Range<u32> {
+ 0..v.map(|(_, v)| v.borrow().bits() as u32).unwrap_or(0)
+}
+
+#[derive(Clone, Debug)]
+pub struct Iter<'a> {
+ internals: Option<IterInternals<enum_map::Iter<'a, LocKind, BigUint>, &'a BigUint>>,
+}
+
+impl Iterator for Iter<'_> {
+ type Item = Loc;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ self.internals.as_mut()?.next()
+ }
+}
+
+impl FusedIterator for Iter<'_> {}
+
+pub struct IntoIter {
+ internals: Option<IterInternals<enum_map::IntoIter<LocKind, BigUint>, BigUint>>,
+}
+
+impl Iterator for IntoIter {
+ type Item = Loc;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ self.internals.as_mut()?.next()
+ }
+}
+
+impl FusedIterator for IntoIter {}
+
+impl IntoIterator for LocSet {
+ type Item = Loc;
+ type IntoIter = IntoIter;
+
+ fn into_iter(self) -> Self::IntoIter {
+ if let Some(ty) = self.ty {
+ let mut starts = self.starts.into_iter().peekable();
+ IntoIter {
+ internals: Some(IterInternals {
+ ty,
+ start_range: get_start_range(starts.peek()),
+ starts,
+ }),
+ }
+ } else {
+ IntoIter { internals: None }
+ }
+ }
+}
+
+impl<'a> IntoIterator for &'a LocSet {
+ type Item = Loc;
+ type IntoIter = Iter<'a>;
+
+ fn into_iter(self) -> Self::IntoIter {
+ self.iter()
+ }
+}
+
+impl Extend<Loc> for LocSet {
+ fn extend<T: IntoIterator<Item = Loc>>(&mut self, iter: T) {
+ iter.into_iter().for_each(|item| {
+ self.insert(item);
+ });
+ }
+}
+
+impl<E: From<Error>> Extend<Loc> for Result<LocSet, E> {
+ fn extend<T: IntoIterator<Item = Loc>>(&mut self, iter: T) {
+ iter.into_iter().try_for_each(|item| {
+ let Ok(loc_set) = self else {
+ return ControlFlow::Break(());
+ };
+ match loc_set.try_insert(item) {
+ Ok(_) => ControlFlow::Continue(()),
+ Err(e) => {
+ *self = Err(e.into());
+ ControlFlow::Break(())
+ }
+ }
+ });
+ }
+}
+
+impl FromIterator<Loc> for LocSet {
+ fn from_iter<T: IntoIterator<Item = Loc>>(iter: T) -> Self {
+ let mut retval = LocSet::new();
+ retval.extend(iter);
+ retval
+ }
+}
+
+impl<E: From<Error>> FromIterator<Loc> for Result<LocSet, E> {
+ fn from_iter<T: IntoIterator<Item = Loc>>(iter: T) -> Self {
+ let mut retval = Ok(LocSet::new());
+ retval.extend(iter);
+ retval
+ }
+}
+
+struct HexBigUint<'a>(&'a BigUint);
+
+impl fmt::Debug for HexBigUint<'_> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "{:#x}", self.0)
+ }
+}
+
+struct LocSetStarts<'a>(&'a EnumMap<LocKind, BigUint>);
+
+impl fmt::Debug for LocSetStarts<'_> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_map()
+ .entries(self.0.iter().map(|(k, v)| (k, HexBigUint(v))))
+ .finish()
+ }
+}
+
+impl fmt::Debug for LocSet {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("LocSet")
+ .field("starts", &self.starts)
+ .finish()
+ }
+}
+
+macro_rules! impl_bin_op {
+ (
+ $bin_op:ident::$bin_op_fn:ident(),
+ $bin_assign_op:ident::$bin_assign_op_fn:ident(),
+ $starts_op:expr,
+ $handle_unequal_types:expr,
+ $update_unequal_types:expr,
+ ) => {
+ impl $bin_op<&'_ LocSet> for &'_ LocSet {
+ type Output = LocSet;
+
+ fn $bin_op_fn(self, rhs: &'_ LocSet) -> Self::Output {
+ if self.ty != rhs.ty {
+ $handle_unequal_types(self, Cow::<LocSet>::Borrowed(rhs))
+ } else {
+ LocSet {
+ starts: enum_map! {kind => $starts_op(&self.starts[kind], &rhs.starts[kind])},
+ ty: self.ty,
+ }
+ }
+ }
+ }
+
+ impl $bin_assign_op<&'_ LocSet> for LocSet {
+ fn $bin_assign_op_fn(&mut self, rhs: &'_ LocSet) {
+ if self.ty != rhs.ty {
+ $update_unequal_types(self, rhs);
+ } else {
+ for (kind, starts) in &mut self.starts {
+ let v: BigUint = std::mem::take(starts);
+ *starts = $starts_op(v, &rhs.starts[kind]);
+ }
+ }
+ }
+ }
+
+ impl $bin_assign_op<LocSet> for LocSet {
+ fn $bin_assign_op_fn(&mut self, rhs: LocSet) {
+ self.$bin_assign_op_fn(&rhs);
+ }
+ }
+
+ impl $bin_op<&'_ LocSet> for LocSet {
+ type Output = LocSet;
+
+ fn $bin_op_fn(mut self, rhs: &'_ LocSet) -> Self::Output {
+ self.$bin_assign_op_fn(rhs);
+ self
+ }
+ }
+
+ impl $bin_op<LocSet> for LocSet {
+ type Output = LocSet;
+
+ fn $bin_op_fn(mut self, rhs: LocSet) -> Self::Output {
+ self.$bin_assign_op_fn(rhs);
+ self
+ }
+ }
+
+ impl $bin_op<LocSet> for &'_ LocSet {
+ type Output = LocSet;
+
+ fn $bin_op_fn(self, mut rhs: LocSet) -> Self::Output {
+ if self.ty != rhs.ty {
+ $handle_unequal_types(self, Cow::<LocSet>::Owned(rhs))
+ } else {
+ for (kind, starts) in &mut rhs.starts {
+ *starts = $starts_op(&self.starts[kind], std::mem::take(starts));
+ }
+ rhs
+ }
+ }
+ }
+ };
+}
+
+impl_bin_op! {
+ BitAnd::bitand(),
+ BitAndAssign::bitand_assign(),
+ BitAnd::bitand,
+ |_, _| LocSet::new(),
+ |lhs, _| LocSet::clear(lhs),
+}
+
+impl_bin_op! {
+ BitOr::bitor(),
+ BitOrAssign::bitor_assign(),
+ BitOr::bitor,
+ |lhs: &LocSet, rhs: Cow<LocSet>| panic!("{}", Error::TyMismatch { ty: rhs.ty, expected_ty: lhs.ty }),
+ |lhs: &mut LocSet, rhs: &LocSet| panic!("{}", Error::TyMismatch { ty: rhs.ty, expected_ty: lhs.ty }),
+}
+
+impl_bin_op! {
+ BitXor::bitxor(),
+ BitXorAssign::bitxor_assign(),
+ BitXor::bitxor,
+ |lhs: &LocSet, rhs: Cow<LocSet>| panic!("{}", Error::TyMismatch { ty: rhs.ty, expected_ty: lhs.ty }),
+ |lhs: &mut LocSet, rhs: &LocSet| panic!("{}", Error::TyMismatch { ty: rhs.ty, expected_ty: lhs.ty }),
+}
+
+impl_bin_op! {
+ Sub::sub(),
+ SubAssign::sub_assign(),
+ and_not,
+ |lhs: &LocSet, _| lhs.clone(),
+ |_, _| {},
+}
+
+/// the largest number of Locs in `lhs` that a single Loc
+/// from `rhs` can conflict with
+#[derive(Clone)]
+pub struct LocSetMaxConflictsWith<Rhs> {
+ lhs: Interned<LocSet>,
+ rhs: Rhs,
+ // result is not included in equality or hash
+ result: Cell<Option<u32>>,
+}
+
+impl<Rhs: Hash> Hash for LocSetMaxConflictsWith<Rhs> {
+ fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
+ self.lhs.hash(state);
+ self.rhs.hash(state);
+ }
+}
+
+impl<Rhs: Eq> Eq for LocSetMaxConflictsWith<Rhs> {}
+
+impl<Rhs: PartialEq> PartialEq for LocSetMaxConflictsWith<Rhs> {
+ fn eq(&self, other: &Self) -> bool {
+ self.lhs == other.lhs && self.rhs == other.rhs
+ }
+}
+
+pub trait LocSetMaxConflictsWithTrait: Clone {
+ fn intern(
+ v: LocSetMaxConflictsWith<Self>,
+ global_state: &GlobalState,
+ ) -> Interned<LocSetMaxConflictsWith<Self>>;
+ fn compute_result(lhs: &Interned<LocSet>, rhs: &Self, global_state: &GlobalState) -> u32;
+}
+
+impl LocSetMaxConflictsWithTrait for Loc {
+ fn compute_result(lhs: &Interned<LocSet>, rhs: &Self, _global_state: &GlobalState) -> u32 {
+ // now we do the equivalent of:
+ // return lhs.iter().map(|loc| rhs.conflicts(loc) as u32).sum().unwrap_or(0)
+ let Some(reg_len) = lhs.reg_len() else {
+ return 0;
+ };
+ let starts = &lhs.starts[rhs.kind];
+ if starts.is_zero() {
+ return 0;
+ }
+ // now we do the equivalent of:
+ // return sum(rhs.start < start + reg_len
+ // and start < rhs.start + rhs.reg_len
+ // for start in starts)
+ let stops = starts << reg_len.get();
+
+ // find all the bit indexes `i` where `i < rhs.start + 1`
+ let lt_rhs_start_plus_1 = (BigUint::from(1u32) << (rhs.start + 1)) - 1u32;
+
+ // find all the bit indexes `i` where
+ // `i < rhs.start + rhs.reg_len + reg_len`
+ let lt_rhs_start_plus_rhs_reg_len_plus_reg_len =
+ (BigUint::from(1u32) << (rhs.start + rhs.reg_len.get() + reg_len.get())) - 1u32;
+ let mut included = and_not(&stops, &stops & lt_rhs_start_plus_1);
+ included &= lt_rhs_start_plus_rhs_reg_len_plus_reg_len;
+ included.count_ones() as u32
+ }
+
+ fn intern(
+ v: LocSetMaxConflictsWith<Self>,
+ global_state: &GlobalState,
+ ) -> Interned<LocSetMaxConflictsWith<Self>> {
+ v.into_interned(global_state)
+ }
+}
+
+impl LocSetMaxConflictsWithTrait for Interned<LocSet> {
+ fn compute_result(lhs: &Interned<LocSet>, rhs: &Self, global_state: &GlobalState) -> u32 {
+ rhs.iter()
+ .map(|loc| lhs.clone().max_conflicts_with(loc, global_state))
+ .max()
+ .unwrap_or(0)
+ }
+
+ fn intern(
+ v: LocSetMaxConflictsWith<Self>,
+ global_state: &GlobalState,
+ ) -> Interned<LocSetMaxConflictsWith<Self>> {
+ v.into_interned(global_state)
+ }
+}
+
+impl<Rhs: LocSetMaxConflictsWithTrait> LocSetMaxConflictsWith<Rhs> {
+ pub fn lhs(&self) -> &Interned<LocSet> {
+ &self.lhs
+ }
+ pub fn rhs(&self) -> &Rhs {
+ &self.rhs
+ }
+ pub fn result(&self, global_state: &GlobalState) -> u32 {
+ match self.result.get() {
+ Some(v) => v,
+ None => {
+ let retval = Rhs::compute_result(&self.lhs, &self.rhs, global_state);
+ self.result.set(Some(retval));
+ retval
+ }
+ }
+ }
+}
+
+impl Interned<LocSet> {
+ pub fn max_conflicts_with<Rhs>(self, rhs: Rhs, global_state: &GlobalState) -> u32
+ where
+ Rhs: LocSetMaxConflictsWithTrait,
+ LocSetMaxConflictsWith<Rhs>: InternTarget,
+ {
+ LocSetMaxConflictsWithTrait::intern(
+ LocSetMaxConflictsWith {
+ lhs: self,
+ rhs,
+ result: Cell::default(),
+ },
+ global_state,
+ )
+ .result(global_state)
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ #[test]
+ fn test_and_not() {
+ for a in 0..0x10u32 {
+ for b in 0..0x10 {
+ assert_eq!(
+ and_not(&BigUint::from(a), BigUint::from(b)),
+ (a & !b).into()
+ );
+ }
+ }
+ }
}
projects / bigint-presentation-code.git / commitdiff