use crate::block::{ItemContent, ItemPtr};
use crate::slice::ItemSlice;
use crate::{Assoc, ReadTxn, StickyIndex, Value};
use smallvec::{smallvec, SmallVec};
use std::ops::Deref;
pub(crate) trait BlockIterator: TxnIterator<Item = ItemPtr> + Sized {
#[inline]
fn slices(self) -> BlockSlices<Self> {
BlockSlices(self)
}
#[inline]
fn within_range(self, from: StickyIndex, to: StickyIndex) -> RangeIter<Self> {
RangeIter::new(self, from, to)
}
}
impl<T> BlockIterator for T where T: TxnIterator<Item = ItemPtr> + Sized {}
pub(crate) trait BlockSliceIterator: TxnIterator<Item = ItemSlice> + Sized {
#[inline]
fn values(self) -> Values<Self> {
Values::new(self)
}
}
impl<T> BlockSliceIterator for T where T: TxnIterator<Item = ItemSlice> + Sized {}
pub trait IntoBlockIter {
fn to_iter(self) -> BlockIter;
}
impl IntoBlockIter for Option<ItemPtr> {
#[inline]
fn to_iter(self) -> BlockIter {
BlockIter(self)
}
}
#[repr(transparent)]
#[derive(Debug, Clone)]
pub struct BlockIter(Option<ItemPtr>);
impl BlockIter {
#[inline]
fn new(ptr: Option<ItemPtr>) -> Self {
BlockIter(ptr)
}
pub fn moved(self) -> MoveIter {
MoveIter::new(self)
}
}
impl Iterator for BlockIter {
type Item = ItemPtr;
fn next(&mut self) -> Option<Self::Item> {
let curr = self.0.take();
if let Some(item) = curr.as_deref() {
self.0 = item.right;
}
curr
}
}
impl DoubleEndedIterator for BlockIter {
fn next_back(&mut self) -> Option<Self::Item> {
let curr = self.0.take();
if let Some(item) = curr.as_deref() {
self.0 = item.left;
}
curr
}
}
impl IntoIterator for ItemPtr {
type Item = ItemPtr;
type IntoIter = BlockIter;
fn into_iter(self) -> Self::IntoIter {
BlockIter::new(Some(self))
}
}
pub trait TxnIterator {
type Item;
fn next<T: ReadTxn>(&mut self, txn: &T) -> Option<Self::Item>;
fn collect<T, B>(&mut self, txn: &T) -> B
where
T: ReadTxn,
B: Default + Extend<Self::Item>,
{
let mut buf = B::default();
while let Some(item) = self.next(txn) {
buf.extend([item]);
}
buf
}
}
pub trait TxnDoubleEndedIterator: TxnIterator {
fn next_back<T: ReadTxn>(&mut self, txn: &T) -> Option<Self::Item>;
}
#[derive(Debug)]
pub struct MoveIter {
iter: BlockIter,
stack: MoveStack,
}
impl MoveIter {
pub(crate) fn new(iter: BlockIter) -> Self {
MoveIter {
iter,
stack: MoveStack::default(),
}
}
fn escape_current_scope(&mut self) -> bool {
if let Some(scope) = self.stack.pop() {
self.iter = scope.dest.into_iter();
true
} else {
false
}
}
}
impl TxnIterator for MoveIter {
type Item = ItemPtr;
fn next<T: ReadTxn>(&mut self, txn: &T) -> Option<Self::Item> {
while {
if let Some(curr) = self.iter.next() {
let scope = self.stack.current_scope();
let ctx = scope.map(|s| s.dest);
if curr.moved == ctx {
if let Some(scope) = scope {
if scope.end == Some(curr) {
self.escape_current_scope();
self.iter.next();
}
}
if let ItemContent::Move(m) = &curr.content {
let (start, end) = m.get_moved_coords(txn);
self.stack.push(MoveScope::new(start, end, curr));
self.iter = BlockIter(start);
} else {
return Some(curr);
}
}
true } else {
let escaped = self.escape_current_scope();
self.iter.next();
escaped
}
} {}
None
}
}
impl TxnDoubleEndedIterator for MoveIter {
fn next_back<T: ReadTxn>(&mut self, txn: &T) -> Option<Self::Item> {
while {
if let Some(curr) = self.iter.next_back() {
let scope = self.stack.current_scope();
if curr.moved == scope.map(|s| s.dest) {
if let Some(scope) = scope {
if scope.start == Some(curr) {
self.escape_current_scope();
self.iter.next_back();
}
}
if let ItemContent::Move(m) = &curr.content {
let (start, end) = m.get_moved_coords(txn);
self.stack.push(MoveScope::new(start, end, curr));
self.iter = BlockIter(end);
} else {
return Some(curr);
}
}
true } else {
let escaped = self.escape_current_scope();
self.iter.next_back();
escaped
}
} {}
None
}
}
#[derive(Debug, Default)]
struct MoveStack(Option<Vec<MoveScope>>);
impl MoveStack {
fn current_scope(&self) -> Option<&MoveScope> {
if let Some(stack) = &self.0 {
stack.last()
} else {
None
}
}
fn push(&mut self, scope: MoveScope) {
let stack = self.0.get_or_insert_with(Vec::default);
stack.push(scope);
}
fn pop(&mut self) -> Option<MoveScope> {
if let Some(stack) = &mut self.0 {
stack.pop()
} else {
None
}
}
}
#[derive(Debug)]
struct MoveScope {
start: Option<ItemPtr>,
end: Option<ItemPtr>,
dest: ItemPtr,
}
impl MoveScope {
fn new(start: Option<ItemPtr>, end: Option<ItemPtr>, dest: ItemPtr) -> Self {
MoveScope { start, end, dest }
}
}
#[derive(Debug)]
pub(crate) struct BlockSlices<I>(I)
where
I: TxnIterator<Item = ItemPtr> + Sized;
impl<I> TxnIterator for BlockSlices<I>
where
I: TxnIterator<Item = ItemPtr> + Sized,
{
type Item = ItemSlice;
fn next<T: ReadTxn>(&mut self, txn: &T) -> Option<Self::Item> {
let ptr = self.0.next(txn)?;
Some(ptr.into())
}
}
impl<I> TxnDoubleEndedIterator for BlockSlices<I>
where
I: TxnDoubleEndedIterator<Item = ItemPtr>,
{
fn next_back<T: ReadTxn>(&mut self, txn: &T) -> Option<Self::Item> {
let ptr = self.0.next_back(txn)?;
Some(ptr.into())
}
}
#[derive(Debug)]
pub(crate) struct RangeIter<I> {
iter: I,
start: StickyIndex,
end: StickyIndex,
state: RangeIterState,
}
impl<I> RangeIter<I>
where
I: TxnIterator<Item = ItemPtr>,
{
fn new(iter: I, start: StickyIndex, end: StickyIndex) -> Self {
RangeIter {
iter,
start,
end,
state: RangeIterState::Opened,
}
}
fn begin<T: ReadTxn>(&mut self, txn: &T, start_offset: &mut u32) -> Option<ItemPtr> {
let mut offset = 0;
let mut curr = self.iter.next(txn);
while let Some(ptr) = curr {
match self.start.id() {
None => {
self.state = RangeIterState::InRange;
break;
}
Some(start) if ptr.contains(start) => {
self.state = RangeIterState::InRange;
offset = start.clock - ptr.id().clock;
if self.start.assoc == Assoc::After {
offset += 1;
if offset == ptr.len() {
offset = 0;
curr = self.iter.next(txn);
}
}
break;
}
_ => curr = self.iter.next(txn),
}
}
*start_offset = offset;
curr
}
}
impl<I> TxnIterator for RangeIter<I>
where
I: TxnIterator<Item = ItemPtr>,
{
type Item = ItemSlice;
fn next<T: ReadTxn>(&mut self, txn: &T) -> Option<Self::Item> {
let mut start_offset = 0;
let ptr = match self.state {
RangeIterState::Opened => {
self.begin(txn, &mut start_offset)
}
RangeIterState::InRange => self.iter.next(txn),
RangeIterState::Closed => return None,
}?;
let end_offset = match self.end.id() {
Some(end) if ptr.contains(end) => {
self.state = RangeIterState::Closed;
let mut offset = end.clock - ptr.id().clock;
if self.end.assoc == Assoc::Before {
if offset == start_offset {
return None;
}
offset -= 1;
}
offset
}
_ => ptr.len() - 1,
};
Some(ItemSlice::new(ptr, start_offset, end_offset))
}
}
impl<I> TxnDoubleEndedIterator for RangeIter<I>
where
I: TxnDoubleEndedIterator<Item = ItemPtr>,
{
fn next_back<T: ReadTxn>(&mut self, txn: &T) -> Option<Self::Item> {
let mut end_offset = 0;
let ptr = match self.state {
RangeIterState::InRange => self.iter.next_back(txn),
RangeIterState::Opened => {
let mut curr = self.iter.next_back(txn);
while let Some(ptr) = curr {
end_offset = ptr.len();
match self.end.id() {
None => {
self.state = RangeIterState::InRange;
break;
}
Some(end) if ptr.contains(end) => {
self.state = RangeIterState::InRange;
end_offset = end.clock - ptr.id().clock;
break;
}
_ => curr = self.iter.next_back(txn),
}
}
curr
}
RangeIterState::Closed => return None,
}?;
let start_offset = match self.start.id() {
Some(start) if ptr.contains(start) => {
self.state = RangeIterState::Closed;
start.clock - ptr.id().clock
}
_ => 0,
};
Some(ItemSlice::new(ptr, start_offset, end_offset))
}
}
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
enum RangeIterState {
Opened,
InRange,
Closed,
}
#[derive(Debug)]
pub(crate) struct Values<I> {
iter: I,
current: Option<ItemSlice>,
}
impl<I> Values<I> {
fn new(iter: I) -> Self {
Values {
iter,
current: None,
}
}
}
impl<I> TxnIterator for Values<I>
where
I: TxnIterator<Item = ItemSlice>,
{
type Item = Value;
fn next<T: ReadTxn>(&mut self, txn: &T) -> Option<Self::Item> {
loop {
if let Some(slice) = &mut self.current {
if slice.start <= slice.end {
let item = slice.ptr.deref();
if !item.is_deleted() {
let mut buf = [Value::default()];
let read = item.content.read(slice.start as usize, &mut buf);
if read != 0 {
slice.start += read as u32;
return Some(std::mem::take(&mut buf[0]));
}
}
}
}
self.current = Some(self.iter.next(txn)?);
}
}
fn collect<T, B>(&mut self, txn: &T) -> B
where
T: ReadTxn,
B: Default + Extend<Self::Item>,
{
fn read_slice<B>(slice: ItemSlice, buf: &mut B)
where
B: Extend<Value>,
{
let item = slice.ptr.deref();
if !item.is_deleted() {
let size = slice.end - slice.start + 1;
let mut b: SmallVec<[Value; 2]> = smallvec![Value::default(); size as usize];
let _ = item.content.read(slice.start as usize, b.as_mut_slice());
buf.extend(b);
}
}
let mut buf = B::default();
if let Some(slice) = self.current.take() {
read_slice(slice, &mut buf);
}
while let Some(slice) = self.iter.next(txn) {
read_slice(slice, &mut buf);
}
buf
}
}
#[derive(Debug)]
pub struct AsIter<'a, T, I> {
txn: &'a T,
iter: I,
}
impl<'a, T, I> AsIter<'a, T, I>
where
T: ReadTxn,
I: TxnIterator,
{
pub fn new(iter: I, txn: &'a T) -> Self {
AsIter { txn, iter }
}
}
impl<'a, T, I> Iterator for AsIter<'a, T, I>
where
T: ReadTxn,
I: TxnIterator,
{
type Item = I::Item;
fn next(&mut self) -> Option<Self::Item> {
self.iter.next(self.txn)
}
}
#[cfg(test)]
mod test {
use crate::iter::{BlockIterator, BlockSliceIterator, IntoBlockIter, TxnIterator};
use crate::test_utils::exchange_updates;
use crate::{Array, Assoc, Doc, StickyIndex, Transact, ID};
#[test]
fn move_last_elem_iter() {
let doc = Doc::with_client_id(1);
let array = doc.get_or_insert_array("array");
let mut txn = doc.transact_mut();
array.insert_range(&mut txn, 0, [1, 2, 3]);
drop(txn);
let mut txn = doc.transact_mut();
array.move_to(&mut txn, 2, 0);
let start = array.as_ref().start;
let mut i = start.to_iter().moved().slices().values();
assert_eq!(i.next(&txn), Some(3.into()));
assert_eq!(i.next(&txn), Some(1.into()));
assert_eq!(i.next(&txn), Some(2.into()));
assert_eq!(i.next(&txn), None);
}
#[test]
fn move_1() {
let d1 = Doc::with_client_id(1);
let a1 = d1.get_or_insert_array("array");
let d2 = Doc::with_client_id(2);
let a2 = d2.get_or_insert_array("array");
{
let mut txn = d1.transact_mut();
a1.insert_range(&mut txn, 0, [1, 2, 3]);
a1.move_to(&mut txn, 1, 0);
}
{
let txn = d1.transact();
let mut i = a1.as_ref().start.to_iter().moved().slices().values();
assert_eq!(i.next(&txn), Some(2.into()));
assert_eq!(i.next(&txn), Some(1.into()));
assert_eq!(i.next(&txn), Some(3.into()));
assert_eq!(i.next(&txn), None);
}
exchange_updates(&[&d1, &d2]);
{
let txn = d2.transact();
let mut i = a2.as_ref().start.to_iter().moved().slices().values();
assert_eq!(i.next(&txn), Some(2.into()));
assert_eq!(i.next(&txn), Some(1.into()));
assert_eq!(i.next(&txn), Some(3.into()));
assert_eq!(i.next(&txn), None);
}
a1.move_to(&mut d1.transact_mut(), 0, 2);
{
let txn = d1.transact();
let mut i = a1.as_ref().start.to_iter().moved().slices().values();
assert_eq!(i.next(&txn), Some(1.into()));
assert_eq!(i.next(&txn), Some(2.into()));
assert_eq!(i.next(&txn), Some(3.into()));
assert_eq!(i.next(&txn), None);
}
}
#[test]
fn move_2() {
let d1 = Doc::with_client_id(1);
let a1 = d1.get_or_insert_array("array");
let d2 = Doc::with_client_id(2);
let a2 = d2.get_or_insert_array("array");
a1.insert_range(&mut d1.transact_mut(), 0, [1, 2]);
a1.move_to(&mut d1.transact_mut(), 1, 0);
{
let txn = d1.transact();
let mut i = a1.as_ref().start.to_iter().moved().slices().values();
assert_eq!(i.next(&txn), Some(2.into()));
assert_eq!(i.next(&txn), Some(1.into()));
assert_eq!(i.next(&txn), None);
}
exchange_updates(&[&d1, &d2]);
{
let txn = d2.transact();
let mut i = a2.as_ref().start.to_iter().moved().slices().values();
assert_eq!(i.next(&txn), Some(2.into()));
assert_eq!(i.next(&txn), Some(1.into()));
assert_eq!(i.next(&txn), None);
}
a1.move_to(&mut d1.transact_mut(), 0, 2);
{
let txn = d1.transact();
let mut i = a1.as_ref().start.to_iter().moved().slices().values();
assert_eq!(i.next(&txn), Some(1.into()));
assert_eq!(i.next(&txn), Some(2.into()));
assert_eq!(i.next(&txn), None);
}
}
#[test]
fn move_cycles() {
let d1 = Doc::with_client_id(1);
let a1 = d1.get_or_insert_array("array");
let d2 = Doc::with_client_id(2);
let a2 = d2.get_or_insert_array("array");
a1.insert_range(&mut d1.transact_mut(), 0, [1, 2, 3, 4]);
exchange_updates(&[&d1, &d2]);
a1.move_range_to(&mut d1.transact_mut(), 0, Assoc::After, 1, Assoc::Before, 3);
{
let txn = d1.transact();
let mut i = a1.as_ref().start.to_iter().moved().slices().values();
assert_eq!(i.next(&txn), Some(3.into()));
assert_eq!(i.next(&txn), Some(1.into()));
assert_eq!(i.next(&txn), Some(2.into()));
assert_eq!(i.next(&txn), Some(4.into()));
assert_eq!(i.next(&txn), None);
}
a2.move_range_to(&mut d2.transact_mut(), 2, Assoc::After, 3, Assoc::Before, 1);
{
let txn = d2.transact();
let mut i = a2.as_ref().start.to_iter().moved().slices().values();
assert_eq!(i.next(&txn), Some(1.into()));
assert_eq!(i.next(&txn), Some(3.into()));
assert_eq!(i.next(&txn), Some(4.into()));
assert_eq!(i.next(&txn), Some(2.into()));
assert_eq!(i.next(&txn), None);
}
exchange_updates(&[&d1, &d2]);
exchange_updates(&[&d1, &d2]); let t1 = d1.transact();
let v1: Vec<_> = a1
.as_ref()
.start
.to_iter()
.moved()
.slices()
.values()
.collect(&t1);
let t2 = d2.transact();
let v2: Vec<_> = a2
.as_ref()
.start
.to_iter()
.moved()
.slices()
.values()
.collect(&t2);
assert_eq!(v1, v2);
}
#[test]
fn range_bounded() {
let doc = Doc::with_client_id(1);
let array = doc.get_or_insert_array("array");
array.insert_range(&mut doc.transact_mut(), 0, [2, 3, 4]);
array.insert_range(&mut doc.transact_mut(), 0, [1]);
array.insert_range(&mut doc.transact_mut(), 4, [5, 6]);
let txn = doc.transact();
let from = StickyIndex::from_id(ID::new(1, 1), Assoc::Before);
let to = StickyIndex::from_id(ID::new(1, 4), Assoc::After);
let res: Vec<_> = array
.as_ref()
.start
.to_iter()
.moved()
.within_range(from, to)
.values()
.collect(&txn);
assert_eq!(res, vec![3.into(), 4.into(), 5.into()])
}
#[test]
fn range_left_exclusive() {
let doc = Doc::with_client_id(1);
let array = doc.get_or_insert_array("array");
array.insert_range(&mut doc.transact_mut(), 0, [2, 3, 4]);
array.insert_range(&mut doc.transact_mut(), 0, [1]);
array.insert_range(&mut doc.transact_mut(), 4, [5, 6]);
let txn = doc.transact();
let from = StickyIndex::from_id(ID::new(1, 1), Assoc::After);
let to = StickyIndex::from_id(ID::new(1, 4), Assoc::After);
let res: Vec<_> = array
.as_ref()
.start
.to_iter()
.moved()
.within_range(from, to)
.values()
.collect(&txn);
assert_eq!(res, vec![4.into(), 5.into()])
}
#[test]
fn range_left_exclusive_2() {
let doc = Doc::with_client_id(1);
let array = doc.get_or_insert_array("array");
array.insert_range(&mut doc.transact_mut(), 0, [2, 3, 4]);
array.insert_range(&mut doc.transact_mut(), 0, [1]);
array.insert_range(&mut doc.transact_mut(), 4, [5, 6]);
let txn = doc.transact();
let from = StickyIndex::from_id(ID::new(1, 2), Assoc::After);
let to = StickyIndex::from_id(ID::new(1, 4), Assoc::After);
let res: Vec<_> = array
.as_ref()
.start
.to_iter()
.moved()
.within_range(from, to)
.values()
.collect(&txn);
assert_eq!(res, vec![5.into()])
}
#[test]
fn range_right_exclusive() {
let doc = Doc::with_client_id(1);
let array = doc.get_or_insert_array("array");
array.insert_range(&mut doc.transact_mut(), 0, [2, 3, 4]);
array.insert_range(&mut doc.transact_mut(), 0, [1]);
array.insert_range(&mut doc.transact_mut(), 4, [5, 6]);
let txn = doc.transact();
let from = StickyIndex::from_id(ID::new(1, 1), Assoc::Before);
let to = StickyIndex::from_id(ID::new(1, 5), Assoc::Before);
let res: Vec<_> = array
.as_ref()
.start
.to_iter()
.moved()
.within_range(from, to)
.values()
.collect(&txn);
assert_eq!(res, vec![3.into(), 4.into(), 5.into()])
}
#[test]
fn range_right_exclusive_2() {
let doc = Doc::with_client_id(1);
let array = doc.get_or_insert_array("array");
array.insert_range(&mut doc.transact_mut(), 0, [2, 3, 4]);
array.insert_range(&mut doc.transact_mut(), 0, [1]);
array.insert_range(&mut doc.transact_mut(), 4, [5, 6]);
let txn = doc.transact();
let from = StickyIndex::from_id(ID::new(1, 1), Assoc::Before);
let to = StickyIndex::from_id(ID::new(1, 4), Assoc::Before);
let res: Vec<_> = array
.as_ref()
.start
.to_iter()
.moved()
.within_range(from, to)
.values()
.collect(&txn);
assert_eq!(res, vec![3.into(), 4.into()])
}
#[test]
fn range_unbounded() {
let doc = Doc::with_client_id(1);
let array = doc.get_or_insert_array("array");
array.insert_range(&mut doc.transact_mut(), 0, [2, 3, 4]);
array.insert_range(&mut doc.transact_mut(), 0, [1]);
array.insert_range(&mut doc.transact_mut(), 4, [5, 6]);
let txn = doc.transact();
let from = StickyIndex::from_type(&txn, &array, Assoc::Before);
let to = StickyIndex::from_type(&txn, &array, Assoc::After);
let res: Vec<_> = array
.as_ref()
.start
.to_iter()
.moved()
.within_range(from, to)
.values()
.collect(&txn);
assert_eq!(
res,
vec![1.into(), 2.into(), 3.into(), 4.into(), 5.into(), 6.into()]
)
}
#[test]
fn range_left_unbounded() {
let doc = Doc::with_client_id(1);
let array = doc.get_or_insert_array("array");
array.insert_range(&mut doc.transact_mut(), 0, [2, 3, 4]);
array.insert_range(&mut doc.transact_mut(), 0, [1]);
array.insert_range(&mut doc.transact_mut(), 4, [5, 6]);
let txn = doc.transact();
let from = StickyIndex::from_type(&txn, &array, Assoc::Before);
let to = StickyIndex::from_id(ID::new(1, 2), Assoc::After);
let res: Vec<_> = array
.as_ref()
.start
.to_iter()
.moved()
.within_range(from, to)
.values()
.collect(&txn);
assert_eq!(res, vec![1.into(), 2.into(), 3.into(), 4.into()])
}
#[test]
fn range_right_unbounded() {
let doc = Doc::with_client_id(1);
let array = doc.get_or_insert_array("array");
array.insert_range(&mut doc.transact_mut(), 0, [2, 3, 4]);
array.insert_range(&mut doc.transact_mut(), 0, [1]);
array.insert_range(&mut doc.transact_mut(), 4, [5, 6]);
let txn = doc.transact();
let from = StickyIndex::from_id(ID::new(1, 2), Assoc::Before);
let to = StickyIndex::from_type(&txn, &array, Assoc::After);
let res: Vec<_> = array
.as_ref()
.start
.to_iter()
.moved()
.within_range(from, to)
.values()
.collect(&txn);
assert_eq!(res, vec![4.into(), 5.into(), 6.into()])
}
#[test]
fn range_single_slice() {
let doc = Doc::with_client_id(1);
let array = doc.get_or_insert_array("array");
array.insert_range(&mut doc.transact_mut(), 0, [2, 3, 4]);
array.insert_range(&mut doc.transact_mut(), 0, [1]);
array.insert_range(&mut doc.transact_mut(), 4, [5, 6]);
let txn = doc.transact();
let from = StickyIndex::from_id(ID::new(1, 1), Assoc::Before);
let to = StickyIndex::from_id(ID::new(1, 1), Assoc::After);
let res: Vec<_> = array
.as_ref()
.start
.to_iter()
.moved()
.within_range(from, to)
.values()
.collect(&txn);
assert_eq!(res, vec![3.into()])
}
}