diff --git a/src/runtime/ecs.rs b/src/runtime/ecs.rs new file mode 100644 index 0000000000000000000000000000000000000000..90f0a55acb749ebc0015634fe548eeee0c7daa57 --- /dev/null +++ b/src/runtime/ecs.rs @@ -0,0 +1,187 @@ +use crate::common::*; +use crate::runtime::ProtocolS; + +use std::collections::HashMap; + +/// invariant: last element is not zero. +/// => all values out of bounds are implicitly absent. +/// i.e., &[0,1] means {1<<32, 0} while &[0,1] is identical to &[1] and means {1}. + +#[derive(Debug, Default)] +struct BitSet(Vec); +impl BitSet { + #[inline(always)] + fn index_decomposed(index: usize) -> [usize; 2] { + // [chunk_index, chunk_bit] + [index / 32, index % 32] + } + fn set(&mut self, at: usize) { + let [chunk_index, chunk_bit] = Self::index_decomposed(at); + if chunk_index >= self.0.len() { + self.0.resize(chunk_index + 1, 0u32); + } + let chunk = unsafe { + // SAFE! previous line ensures sufficient size + self.0.get_unchecked_mut(chunk_index) + }; + *chunk |= 1 << chunk_bit; + } + fn unset(&mut self, at: usize) { + let [chunk_index, chunk_bit] = Self::index_decomposed(at); + if chunk_index < self.0.len() { + let chunk = unsafe { + // SAFE! previous line ensures sufficient size + self.0.get_unchecked_mut(chunk_index) + }; + *chunk &= !(1 << chunk_bit); + while let Some(0u32) = self.0.iter().copied().last() { + self.0.pop(); + } + } + } +} + +#[derive(Debug, Default)] +struct BitMasks(HashMap<(ChannelId, bool), BitSet>); + +struct BitChunkIter> { + chunk_iter: I, + next_bit_index: usize, + cached: Option, // None <=> iterator is done +} + +impl> BitChunkIter { + fn new(mut chunk_iter: I) -> Self { + let cached = chunk_iter.next(); + Self { chunk_iter, next_bit_index: 0, cached } + } +} +impl> Iterator for BitChunkIter { + type Item = usize; + fn next(&mut self) -> Option { + loop { + println!("LOOP"); + // get cached chunk. If none exists, iterator is done. + let mut chunk = self.cached?; + if chunk == 0 { + // self.next_bit_index jumps to next multiple of 32 + self.next_bit_index = (self.next_bit_index + 32) & !(32 - 1); + self.cached = self.chunk_iter.next(); + continue; + } + // this chunk encodes 1+ Items to yield + // shift the contents of chunk until the least significant bit is 1 + + #[inline(always)] + fn shifty(chunk: &mut u32, shift_by: usize, next_bit_index: &mut usize) { + if *chunk & ((1 << shift_by) - 1) == 0 { + *next_bit_index += shift_by; + *chunk >>= shift_by; + } + println!("{:#032b}", *chunk); + } + shifty(&mut chunk, 16, &mut self.next_bit_index); + shifty(&mut chunk, 08, &mut self.next_bit_index); + shifty(&mut chunk, 04, &mut self.next_bit_index); + shifty(&mut chunk, 02, &mut self.next_bit_index); + shifty(&mut chunk, 01, &mut self.next_bit_index); + // assert(chunk & 1 == 1) + + self.next_bit_index += 1; + self.cached = Some(chunk >> 1); + if chunk > 0 { + return Some(self.next_bit_index - 1); + } + } + } +} + +/// Returns an iterator over chunks of bits where ALL of the given +/// bitsets have 1. +struct AndChunkIter<'a> { + // this value is not overwritten during iteration + // invariant: !sets.is_empty() + sets: &'a [&'a [u32]], + + next_chunk_index: usize, +} +impl<'a> AndChunkIter<'a> { + fn new(sets: &'a [&'a [u32]]) -> Self { + let sets = if sets.is_empty() { &[&[] as &[_]] } else { sets }; + Self { sets, next_chunk_index: 0 } + } +} +impl Iterator for AndChunkIter<'_> { + type Item = u32; + fn next(&mut self) -> Option { + let old_chunk_index = self.next_chunk_index; + self.next_chunk_index += 1; + self.sets.iter().fold(Some(!0u32), move |a, b| { + let a = a?; + let b = *b.get(old_chunk_index)?; + Some(a & b) + }) + } +} + +/// Returns an iterator over chunks for bits in range 0..bits_to_go but skipping +/// indices for which ANY of the given bitsets has a 1 +struct NoneChunkIter<'a> { + // this value is not overwritten during iteration + // invariant: !sets.is_empty() + sets: &'a [&'a [u32]], + next_chunk_index: usize, + bits_to_go: usize, +} +impl<'a> NoneChunkIter<'a> { + /// a set of bitsets. the u32s of each are in ascending order of significant digits + /// i.e., &[0,1] means {1<<32, 0} while &[0,1] is identical to &[1] and means {1}. + fn new(sets: &'a [&'a [u32]], max_bit: usize) -> Self { + let sets = if sets.is_empty() { &[&[] as &[_]] } else { sets }; + Self { sets, next_chunk_index: 0, bits_to_go: max_bit } + } +} +impl Iterator for NoneChunkIter<'_> { + type Item = u32; + fn next(&mut self) -> Option { + let neutral = match self.bits_to_go { + 0 => None, + x @ 1..=31 => Some(!0u32 >> (32 - x)), + _ => Some(!0u32), + }; + self.bits_to_go = self.bits_to_go.saturating_sub(32); + + let old_chunk_index = self.next_chunk_index; + self.next_chunk_index += 1; + + self.sets.iter().fold(neutral, move |a, b| { + let a = a?; + let b = *b.get(old_chunk_index)?; + Some(a & !b) + }) + } +} + +#[test] +fn test_bit_iter() { + static SETS: &[&[u32]] = &[ + // + &[0b101001, 0b101001], + &[0b100001, 0b101001], + ]; + let _ = BitChunkIter::new(AndChunkIter::new(SETS)); + let iter = BitChunkIter::new(NoneChunkIter::new(SETS, 9)); + let indices = iter.collect::>(); + println!("indices {:?}", indices); +} + +enum Entity { + Payload(Payload), + State(ProtocolS), +} + +fn ecs() { + let entities: Vec = Default::default(); + let assignments: HashMap<(ChannelId, bool), BitSet> = Default::default(); + let to_run: BitSet = Default::default(); +} diff --git a/src/runtime/mod.rs b/src/runtime/mod.rs index 142c00a4bf23e9f9d9e89b5f4a325f37ace80bde..e92c928f9546a889a5c5892e135cb11cf1d759d4 100644 --- a/src/runtime/mod.rs +++ b/src/runtime/mod.rs @@ -7,7 +7,7 @@ pub(crate) mod connector; pub(crate) mod endpoint; pub mod errors; // mod predicate; // TODO later -mod polyp; +mod ecs; mod serde; pub(crate) mod setup; diff --git a/src/runtime/polyp.rs b/src/runtime/polyp.rs deleted file mode 100644 index 9b096e0a209a6488c26699a8d56df8d14bb19b84..0000000000000000000000000000000000000000 --- a/src/runtime/polyp.rs +++ /dev/null @@ -1,285 +0,0 @@ -use crate::common::*; -use crate::runtime::{Predicate, ProtocolS}; -use core::ops::{Index, IndexMut}; -use std::collections::HashMap; -use std::num::NonZeroU32; - -// struct SpeculationBranch { -// inbox: HashMap, -// outbox: HashMap, -// inner: SpeculationBranchInner, -// known: HashMap, -// } -// enum SpeculationBranchInner { -// Leaf(ProtocolS), - -// // invariant: channel_id branching is redundantly represented by true_false branches' known assignments -// // => true_false[0].known[channel_id] == Some(true) -// // => true_false[1].known[channel_id] == Some(false) -// Fork { channel_id: ChannelId, true_false: Box<[SpeculationBranch; 2]> }, -// } - -// impl SpeculationBranch { -// fn new_tree(init: ProtocolS) -> Self { -// SpeculationBranch { -// inbox: Default::default(), -// outbox: Default::default(), -// known: Default::default(), -// inner: SpeculationBranchInner::Leaf(init), -// } -// } - -// fn feed_msg( -// &mut self, -// ekey: Key, -// payload: &Payload, -// predicate: &Predicate, -// pred: Option, -// ) { -// use SpeculationBranchInner as Sbi; -// let next_pred = Some(Pred { known: &self.known, prev: pred.as_ref() }); -// match &mut self.inner { -// Sbi::Leaf(_state) => { -// if self.inbox.insert(ekey, payload.clone()).is_none() { -// // run this machine -// } -// } -// Sbi::Fork { channel_id, true_false } => match predicate.query(*channel_id) { -// Some(true) => true_false[0].feed_msg(ekey, payload, predicate, next_pred), // feed true -// Some(false) => true_false[1].feed_msg(ekey, payload, predicate, next_pred), // feed false -// None => { -// // feed to both true and false branches -// for x in true_false.iter_mut() { -// x.feed_msg(ekey, payload, predicate, next_pred); -// } -// } -// }, -// } -// } -// } - -// #[derive(Copy, Clone)] -// struct Pred<'a> { -// known: &'a HashMap, -// prev: Option<&'a Pred<'a>>, -// } - -struct Branch { - state: Option, - speculation: Option, -} -struct Speculation { - on: ChannelId, - t: Option, - f: Option, -} - -struct Tree { - branches: Vec, // invariant: non-empty. root at index 0 - states: Vec, -} -impl Tree { - /// determine where in the tree the given message should be inserted (based on the predicate). - /// run all machines - fn feed_and_run(&mut self, predicate: Predicate, payload: &Payload) { - let q = Queryable::new(&predicate); - let mut qs = QueryableSubset::new(&q); - self.branches[0].feed_and_run(payload, &q, &mut qs); - } -} - -struct Queryable(Vec<(ChannelId, bool)>); -impl Queryable { - fn new(predicate: &Predicate) -> Self { - let mut vec: Vec<_> = predicate.assigned.iter().map(|(&k, &v)| (k, v)).collect(); - vec.sort_by(|(a, _), (b, _)| a.cmp(b)); - Self(vec) - } - fn query(&self, channel_id: ChannelId) -> Option<(usize, bool)> { - self.0 - .binary_search_by(|(cid, _)| cid.cmp(&channel_id)) - .ok() - .map(|index| (index, self.0[index].1)) - } -} -struct QueryableSubset { - buf: Vec, - prefix_end: usize, -} -impl QueryableSubset { - fn new(q: &Queryable) -> Self { - let prefix_end = q.0.len(); - Self { buf: (0..prefix_end).collect(), prefix_end } - } - fn remove(&mut self, at: usize) { - self.prefix_end -= 1; - self.buf.swap(self.prefix_end, at); - } - fn undo_remove(&mut self, at: usize) { - self.buf.swap(self.prefix_end, at); - self.prefix_end += 1; - } - fn iter_q<'a: 'b, 'b>( - &'a self, - q: &'b Queryable, - ) -> impl Iterator { - self.buf[..self.prefix_end].iter().map(move |&index| &q.0[index]) - } -} - -impl Branch { - // invariant: q.0 is sorted - // - // invariant: qs.buf[0..qs.prefix_end] is a slice that encodes the set of INDICES in q.0 - // which the path to this branch has NOT queried. - // - // ie. for a given predicate {X=>true, Z=>true, Y=>false} - // => q is [(X,true), (Y,false), (Z,true)] - // => qs is initially [0,1,2] - // and if this branch queries 1, the subtree will receive qs as [0,2] - fn feed_and_run(&mut self, payload: &Payload, q: &Queryable, qs: &mut QueryableSubset) { - match &mut self.speculation { - Some(Speculation { on, t, f }) => { - if let Some((index, assignment)) = q.query(*on) { - // if assignment - } else { - } - todo!() - } - None => { - // - todo!() - } - } - } -} -impl Index for Tree { - type Output = Branch; - fn index(&self, k: BranchKey) -> &Self::Output { - &self.branches[(k.index_plus_one.get() - 1) as usize] - } -} -impl IndexMut for Tree { - fn index_mut(&mut self, k: BranchKey) -> &mut Self::Output { - &mut self.branches[(k.index_plus_one.get() - 1) as usize] - } -} -impl Index for Tree { - type Output = ProtocolS; - fn index(&self, k: StateKey) -> &Self::Output { - &self.states[(k.index_plus_one.get() - 1) as usize] - } -} -impl IndexMut for Tree { - fn index_mut(&mut self, k: StateKey) -> &mut Self::Output { - &mut self.states[(k.index_plus_one.get() - 1) as usize] - } -} - -struct BranchKey { - index_plus_one: NonZeroU32, -} -struct StateKey { - index_plus_one: NonZeroU32, -} - -struct Bitset { - bits: Vec, -} - -struct Polyp { - inbox: Vec, - inbox_masks: BitMasks, - states: Vec, - states_masks: BitMasks, -} - -// invariant: last element is not zero. -// => all values out of bounds are implicitly absent -#[derive(Debug, Default)] -struct BitSet(Vec); - -#[derive(Debug, Default)] -struct BitMasks(HashMap<(ChannelId, bool), BitSet>); - -struct BitSetAndIter<'a> { - // this value is immutable - // invariant: !sets.is_empty() - sets: &'a [&'a [u32]], - next_u32_index: usize, // invariant: in 0..32 while iterating - next_bit_index: usize, - cached: Option, // None <=> iterator is done -} -impl<'a> BitSetAndIter<'a> { - /// a set of bitsets. the u32s of each are in ascending order of significant digits - /// i.e., &[0,1] means {1<<32, 0} while &[0,1] is identical to &[1] and means {1}. - fn new(sets: &'a [&'a [u32]]) -> Self { - const EMPTY_SINGLETON: &[&[u32]] = &[&[]]; - let sets = if sets.is_empty() { EMPTY_SINGLETON } else { sets }; - Self { sets, next_u32_index: 0, next_bit_index: 0, cached: Self::nth_u32(sets, 0) } - } - fn nth_u32(sets: &'a [&'a [u32]], index: usize) -> Option { - sets.iter().fold(Some(!0), |a, b| { - let b = b.get(index)?; - Some(a? & b) - }) - } - fn next_chunk(&mut self) { - self.next_bit_index = 0; - self.next_u32_index += 1; - self.cached = Self::nth_u32(self.sets, self.next_u32_index); - } -} -impl Iterator for BitSetAndIter<'_> { - type Item = usize; - fn next(&mut self) -> Option { - loop { - println!("LOOP"); - // get cached chunk. If none exists, iterator is done. - let mut chunk = self.cached?; - if chunk == 0 { - self.next_chunk(); - continue; - } - // this chunk encodes 1+ Items to yield - // shift the contents of chunk until the least significant bit is 1 - - #[inline(always)] - fn shifty(chunk: &mut u32, shift_by: usize, next_bit_index: &mut usize) { - if *chunk & ((1 << shift_by) - 1) == 0 { - *next_bit_index += shift_by; - *chunk >>= shift_by; - } - println!("{:#032b}", *chunk); - } - shifty(&mut chunk, 16, &mut self.next_bit_index); - shifty(&mut chunk, 08, &mut self.next_bit_index); - shifty(&mut chunk, 04, &mut self.next_bit_index); - shifty(&mut chunk, 02, &mut self.next_bit_index); - shifty(&mut chunk, 01, &mut self.next_bit_index); - // assert(chunk & 1 == 1) - - self.next_bit_index += 1; - self.cached = Some(chunk >> 1); - if chunk > 0 { - let index = self.next_u32_index * 32 + (self.next_bit_index - 1); - // assert((self.next_bit_index-1) < 32) - // because if chunk was shifted 32+ places, its contents would be zero. - return Some(index); - } - } - } -} - -#[test] -fn test_bit_iter() { - static SETS: &[&[u32]] = &[ - // - &[0b1, 0b1, 0b1, 0b1, 0b1], - &[0b1, 0b1, 0b1], - &[0b1, 0b1, 0b0, 0b1], - &[0b1, 0b1, 0b1, 0b1], - ]; - let indices = BitSetAndIter::new(SETS).collect::>(); - println!("indices {:?}", indices); -}