use super::Descendants;
use crate::{
io::SrcID,
mem_use::{MemUsage, MemUser},
ops::{Op, OpID, OpKind},
sort::{noncausal_sort, search_from_back},
sparse_vector::SparseMonotonicVector,
};
use ti64::MsSinceEpoch;
#[derive(Clone, PartialEq, Eq, Hash)]
pub struct InsertOpStore {
pub(crate) start_time: MsSinceEpoch,
pub(crate) per_log: im::HashMap<SrcID, PerLogInsertOpStore>,
}
impl InsertOpStore {
pub(crate) fn for_no_create_yet() -> Self {
InsertOpStore {
start_time: MsSinceEpoch(0),
per_log: im::HashMap::new(),
}
}
pub(crate) fn for_create_op(create: &Op) -> Self {
let mut store = InsertOpStore {
start_time: create.time,
per_log: im::HashMap::new(),
};
let mut per_log_store = PerLogInsertOpStore::default();
per_log_store.has_no_descendants.insert(create.id.1);
store.per_log.insert(create.id.0, per_log_store);
store
}
pub(crate) fn to_vec(&self) -> Vec<Op> {
let mut ops = Vec::new();
for (src_id, per_log) in self.per_log.iter() {
for (idx, _) in per_log.rel_time_and_char.to_vec() {
ops.push(self.get_op(&OpID(*src_id, idx)).unwrap())
}
}
ops
}
}
impl std::fmt::Debug for InsertOpStore {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
write!(f, "InsertOpStore({:?})", self.to_vec())
}
}
#[derive(Clone, Default, PartialEq, Eq, Hash)]
pub struct PerLogInsertOpStore {
pub(crate) rel_time_and_char: SparseMonotonicVector<(i32, u8)>,
pub(crate) full_value: im::OrdMap<u32, litl::Val>,
pub(crate) non_predecessor_prev: im::OrdMap<u32, OpID>,
pub(crate) has_no_descendants: im::OrdSet<u32>,
pub(crate) non_successor_descendants: im::OrdMap<u32, Descendants>,
}
impl InsertOpStore {
pub fn has(&self, id: &OpID) -> bool {
self.per_log
.get(&id.0)
.filter(|per_log| per_log.rel_time_and_char.has_idx(id.1))
.is_some()
}
pub fn get_op(&self, id: &OpID) -> Option<Op> {
self.per_log.get(&id.0).and_then(|per_log| {
per_log.rel_time_and_char.get(id.1).map(|(rel_time, char)| {
let prev = per_log
.non_predecessor_prev
.get(&id.1)
.cloned()
.unwrap_or_else(|| {
if id.1 == 0 {
panic!(
"Op with sequence idx 0 has to have explicit prev. {:?}",
per_log.non_predecessor_prev
)
}
OpID(id.0, id.1 - 1)
});
let val = per_log.full_value.get(&id.1).cloned().unwrap_or_else(|| {
litl::Val::str(unsafe {
std::str::from_utf8_unchecked(std::slice::from_ref(char))
})
});
Op {
id: *id,
prev,
time: MsSinceEpoch(self.start_time.0 + (*rel_time as i64)),
kind: OpKind::ListInsertAfter,
val: Some(val),
}
})
})
}
pub fn get_descendants(&self, id: &OpID) -> Option<Descendants> {
self.per_log.get(&id.0).and_then(|per_log| {
if per_log.has_no_descendants.contains(&id.1) {
None
} else {
Some(
per_log
.non_successor_descendants
.get(&id.1)
.cloned()
.unwrap_or(Descendants::Single(OpID(id.0, id.1 + 1))),
)
}
})
}
pub fn add(&self, op: Op) -> Self {
let mut new = self.clone();
let prev_is_predecessor = (op.id.0 == op.prev.0) && (op.prev.1 == op.id.1 - 1);
let prev_per_log = new
.per_log
.get_mut(&op.prev.0)
.expect("Should have prev_per_log");
if prev_per_log.has_no_descendants.contains(&op.prev.1) {
prev_per_log.has_no_descendants.remove(&op.prev.1);
if !prev_is_predecessor {
prev_per_log
.non_successor_descendants
.insert(op.prev.1, Descendants::Single(op.id));
}
} else {
let default_successor_descendant = OpID(op.prev.0, op.prev.1 + 1);
let descendants = prev_per_log
.non_successor_descendants
.entry(op.prev.1)
.or_insert(Descendants::Single(default_successor_descendant));
let insert_idx = search_from_back(descendants, &op.id, |a_id, b_id| {
let a = if *a_id == op.id {
op.clone()
} else {
self.get_op(a_id).expect("Should have op a")
};
let b = if *b_id == op.id {
op.clone()
} else {
self.get_op(b_id).expect("Should have op b")
};
noncausal_sort(&a, &b).reverse()
})
.expect_err("Should find new insertion position");
descendants.insert(insert_idx, op.id);
}
{
let per_log = new.per_log.entry(op.id.0).or_default();
if !prev_is_predecessor {
per_log.non_predecessor_prev.insert(op.id.1, op.prev);
}
let val = if let (OpKind::ListInsertAfter, Some(val)) = (op.kind, op.val) {
val
} else {
panic!("Expected list insert op in InsertOpStore")
};
match val.direct_ref() {
litl::ValRef::String(string) if string.len() == 1 => {
per_log.rel_time_and_char.insert(
op.id.1,
((op.time.0 - self.start_time.0) as i32, string.as_bytes()[0]),
);
}
_ => {
per_log
.rel_time_and_char
.insert(op.id.1, ((op.time.0 - self.start_time.0) as i32, 0));
per_log.full_value.insert(op.id.1, val);
}
}
per_log.has_no_descendants.insert(op.id.1);
}
new
}
}
impl MemUser for InsertOpStore {
fn mem_use(&self) -> MemUsage {
MemUsage::Struct {
name: "InsertOpStore",
fields: vec![("per_log", self.per_log.mem_use())],
}
}
}
impl MemUser for PerLogInsertOpStore {
fn mem_use(&self) -> MemUsage {
MemUsage::Struct {
name: "PerNodeInsertOpStore",
fields: vec![
("time_and_char", self.rel_time_and_char.mem_use()),
("full_value", self.full_value.mem_use()),
("non_predecessor_prev", self.non_predecessor_prev.mem_use()),
("no_descendant", self.has_no_descendants.mem_use()),
(
"non_successor_descendants",
self.non_successor_descendants.mem_use(),
),
],
}
}
}